Sharp thresholds for nonlinear Hamiltonian cycles in hyerpgraphs. Issue 1 (27th February 2020) - Narayanan, Bhargav; Schacht, Mathias
Abstract : For positive integers r > ℓ, an r ‐uniform hypergraph is called an ℓ ‐cycle if there exists a cyclic ordering of its vertices such that each of its edges consists of r consecutive vertices, and such that every pair of consecutive edges (in the natural ordering of the edges) intersect in precisely ℓ vertices; such cycles are said to be linear when ℓ =1, and nonlinear when ℓ >1. We determine the sharp threshold for nonlinear Hamiltonian cycles and show that for all r > ℓ >1, the threshold p r, ℓ ∗ ( n ) for the appearance of a Hamiltonian ℓ ‐cycle in the random r ‐uniform hypergraph on n vertices is sharp and given by p r, ℓ ∗ ( n ) = λ ( r, ł ) ( e n ) r − ℓ for an explicitly specified function λ . This resolves several questions raised by Dudek and Frieze in 2011.10