Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs. Issue 1 (27th February 2020)

• Record Type: Journal Article
• Authors: Narayanan, Bhargav; Schacht, Mathias
• Is Part Of: Random structures & algorithms. Volume 57:Issue 1(2020)
• Page Start: 244
• Page End: 255
• Publication Date: 2020-02-27
• Subjects: Hamilton cycles -- thresholds -- hypergraphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20919
• Languages: English
• ISSNs: 1042-9832

Abstract

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