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

Let GG(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 bb^* be its threshold bias.

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

pClnnn,p\geq \frac{C\ln n}{n},

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

b=Θ(nplnn).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.

Sources & referencesView supporting material

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.