Degree-threshold conjecture for linear Hamiltonian cycles

Let G(r)(n,p)G^{(r)}(n,p) be the binomial random rr-uniform hypergraph. For r3r\geq 3, define

prdeg(n)=(r1)!lognnr1.p^{\mathrm{deg}}_r(n)=\frac{(r-1)!\log n}{n^{r-1}}.

This is the sharp threshold for the disappearance of isolated vertices. Degree-threshold conjecture. For each r3r\geq 3, prdeg(n)p^{\mathrm{deg}}_r(n) is the sharp threshold for the appearance of a linear Hamiltonian cycle in G(r)(n,p)G^{(r)}(n,p). The paper proves that the appearance of a linear Hamiltonian cycle has a sharp threshold and predicts that it coincides with the isolated-vertex threshold; the coincidence remains open.

Sources & referencesView supporting material

Primary source

Bhargav Narayanan and Mathias Schacht, “Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs”, arXiv:1906.05142 (2019).

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.