Hamiltonian cycle game's threshold conjecture
Hamiltonian cycle game's threshold conjecture
Let be the set of Hamiltonian cycles in . For a family of winning sets , let denote the smallest bias for which Breaker wins the random game on the edges of , and let denote the threshold probability for Maker's win. Hamiltonian cycle game's threshold conjecture. There exists a constant such that
In particular, . This conjecture asserts that the Hamiltonian cycle game has the same threshold behaviour as the connectivity and perfect matching games; the paper establishes corresponding results for several other games but leaves this Hamiltonian-cycle assertion open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Milos Stojakovic and Tibor Szabo, “Positional games on random graphs”, arXiv:math/0601659 (2006).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.