Hamiltonian Berge cycles in random hypergraphs. (8th March 2021)

• Record Type: Journal Article
• Authors: Bal, Deepak; Berkowitz, Ross; Devlin, Pat; Schacht, Mathias
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 2(2021)
• Page Start: 228
• Page End: 238
• Publication Date: 2021-03-08
• Subjects: 05C65, -- 05C45, -- 05C80, -- 05C38, -- 05D40, -- 05C20; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000437
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: In this note we study the emergence of Hamiltonian Berge cycles in random r -uniform hypergraphs. For $r\geq 3$ we prove an optimal stopping time result that if edges are sequentially added to an initially empty r -graph, then as soon as the minimum degree is at least 2, the hypergraph with high probability 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 with high probability has such a cycle. We obtain similar results for weak Berge cycles as well, thus resolving a conjecture of Poole.