Narayanan–Schacht conjecture on the threshold for non-linear Hamilton cycles

Let Gr(n,p)G_r(n,p) be the random rr-uniform hypergraph, and let Cn,(r)C^{(r)}_{n,\ell} be the rr-uniform \ell-cycle on nn vertices. Write Z(Cn,(r))Z(C^{(r)}_{n,\ell}) for the number of copies of Cn,(r)C^{(r)}_{n,\ell} in Gr(n,p)G_r(n,p). For integers r>>1r>\ell>1, assume (r)n(r-\ell)\mid n. Narayanan–Schacht conjecture. If p=p(n)p=p(n) satisfies

E[Z(Cn,(r))],\mathbb{E}[Z(C^{(r)}_{n,\ell})]\longrightarrow\infty,

then

Pr[Cn,(r)Gr(n,p)]1.\Pr\bigl[C^{(r)}_{n,\ell}\subset G_r(n,p)\bigr]\longrightarrow 1.

Narayanan and Schacht proved that the first-moment threshold is sharp, but above that threshold the expected number of cycles can already be exponentially large. The conjecture asks whether divergence of the expectation alone suffices for the appearance of a non-linear Hamilton cycle with high probability.

Sources & referencesView supporting material

Primary source

Byron Chin, “Exact threshold and limiting distribution for non-linear Hamilton cycles”, arXiv:2411.13452 (2025).

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.