Sharp thresholds for nonlinear Hamiltonian cycles in hyerpgraphs

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 ℓ v...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2020-08, Vol.57 (1), p.244-255
Main Authors: Narayanan, Bhargav, Schacht, Mathias
Format: Article
Language:English
Subjects:
Hamilton cycles
hypergraphs
thresholds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 pr,ℓ∗(n) for the appearance of a Hamiltonian ℓ‐cycle in the random r‐uniform hypergraph on n vertices is sharp and given by pr,ℓ∗(n)=λ(r,ł)(en)r−ℓ for an explicitly specified function λ. This resolves several questions raised by Dudek and Frieze in 2011.10
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20919