Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs

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 precisel...

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:
Apexes
Graph theory
Graphs
Citations: Items that this one cites
Items that cite this one
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 for the appearance of a Hamiltonian ℓ ‐cycle in the random r ‐uniform hypergraph on n vertices is sharp and given by 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