Hercules and Hydra, a game on rooted finite trees
Hercules and Hydra
Forte connexité des complexes polyèdraux
Hercules versus Hidden Hydra Helper
L. Kirby and J. Paris introduced the Hercules and Hydra game on rooted trees as a natural example of an undecidable statement in Peano Arithmetic. One can show that Hercules has a “short” strategy (he wins in a primitively recursive number of moves) and also a “long” strategy (the finiteness of the game cannot be proved in Peano Arithmetic). We investigate the conflict of the “short” and “long” intentions (a problem suggested by J. Nešetřil). After each move of Hercules (trying to kill Hydra fast)...
On the union of matching matroids
Ground state incongruence in 2D spin glasses revisited.
On the dimer problem and the Ising problem in finite 3-dimensional lattices.
On the theory of Pfaffian orientations. II: -joins, -cuts, and duality of enumeration.
On the theory of Pfaffian orientations. I: Perfect matchings and permanents.
Jamming and geometric representations of graphs.
Towards the distribution of the size of a largest planar matching and largest planar subgraph in random bipartite graphs.
The Edmonds-Gallai decomposition for the -piece packing problem.
Perfect matching preservers.
Page 1