Kohayakawa–Nagle–Parczyk conjecture on squares of Hamilton cycles in random graphs

Let G(n,p)G(n,p) be the binomial random graph on vertex set [n][n], with each possible edge included independently with probability p=p(n)p=p(n). A square of a Hamilton cycle is the second power of a Hamilton cycle: for some cyclic ordering of the vertices, every pair of vertices at cyclic distance at most two is an edge. Kohayakawa–Nagle–Parczyk conjecture. For every fixed ε>0\varepsilon>0, if

p(1+ε)e/n,p\geq (1+\varepsilon)\sqrt{e/n},

then G(n,p)G(n,p) a.a.s. contains a square of a Hamilton cycle. This is a more precise proposed sufficient condition than the earlier threshold prediction; the supplied passage does not state whether it has been resolved.

Sources & referencesView supporting material

Primary source

Yulin Chang, Jie Han and Lin Sun, “The threshold for powers of tight Hamilton cycles in random hypergraphs”, arXiv:2310.18980 (2023).

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.