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

About 3 years old · traced to

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.

References

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.