Hamiltonian cycle game's threshold conjecture

From papers

Let H{\cal H} be the set of Hamiltonian cycles in KnK_n. For a family of winning sets F{\cal F}, let bFpb_{\cal F}^p denote the smallest bias for which Breaker wins the random game on the edges of G(n,p)G(n,p), and let pFp_{\cal F} denote the threshold probability for Maker's win. Hamiltonian cycle game's threshold conjecture. There exists a constant CC such that

bHp=Θ(pnlogn),pClognn.b_{{\cal H}}^p = \Theta\left(p\frac{n}{\log n}\right), \qquad p\geq C\frac{\log n}{n}.

In particular, pH=lognnp_{{\cal H}}=\frac{\log n}{n}. 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

No solutions have been posted yet.