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

About 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).

The conjecture concerns the asymptotic threshold bias for Hamiltonicity on random boards and remains unresolved in the supplied context.

References

Primary 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.