Hamiltonian Berge cycles in random hypergraphs

Abstract

In this note, we study the emergence of Hamiltonian Berge cycles in random $r$-uniform hypergraphs. For $r\ge 3$, we prove an optimal stopping-time result that if edges are sequently added to an initially empty $r$-graph, then as soon as the minimum degree is at least 2, the hypergraph almost surely has such a cycle. In particular, this determines the threshold probability for Berge Hamiltonicity of the Erdős--Rényi random $r$-graph, and we also show that the $2$-out random $r$-graph almost surely has such a cycle. We obtain similar results for \textit{weak Berge} cycles as well, thus resolving a conjecture of Poole.

10 pages; an earlier arxiv draft of this paper did not have our stopping-time results

References in corpus (2)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• On Weak Hamiltonicity of a Random Hypergraph

Cited by in corpus (2)

• What are higher-order networks?
• Hamilton Cycles in Random Graphs: a bibliography