← All problems

Stojaković–Szabó threshold-bias conjecture for the random-graph Hamiltonicity game

14 years old · traced to

Let G∼G(n,p)G\sim G(n,p) be a random graph on nn labeled vertices, where each pair of vertices is independently included as an edge with probability pp. Let H(G)\mathcal H(G) denote the Maker–Breaker Hamiltonicity game played on the edge set of GG, and let b∗b^* be its threshold bias.

Stojaković–Szabó conjecture. There exists a constant CC such that for every

p≥Cln⁡nn,p\geq \frac{C\ln n}{n},

a random graph G∼G(n,p)G\sim G(n,p) is typically such that

b∗=Θ(npln⁡n).b^*=\Theta\left(\frac{np}{\ln n}\right).
References

Status

  • Solved: Asaf Ferber, Roman Glebov, Michael Krivelevich, and Alon Naor. Biased Games On Random Boards (arXiv preprint, 2013) https://arxiv.org/abs/1210.7618

Source: Asaf Ferber, Roman Glebov, Michael Krivelevich and Alon Naor, “Biased Games On Random Boards”, arXiv:1210.7618 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.