Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs

2019/06/12 by Narayanan, Bhargav, Schacht, Mathias · 2 citations
#05C45) #05C80 (05C65 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1906.05142

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 is p^*_{r, ℓ} (n) = λ(r,ℓ) ((e)/(n))^{r - ℓ} for an explicitly specified function λ. This resolves several questions raised by Dudek and Frieze in 2011.

Cited by

• Loose Hamiltonicity
• Berge Hamilton cycles in a random sparsification of dense hypergraphs

Related

• Exact threshold and limiting distribution for non-linear Hamilton cycles
• Tight Hamilton Cycles in Random Uniform Hypergraphs
• Hamilton ℓ-cycles in randomly-perturbed hypergraphs
• The threshold for loose Hamilton cycles in random hypergraph
• Forbidding Hamilton cycles in uniform hypergraphs