Hamiltonian Berge cycles in random hypergraphs

Deepak Bal, Ross Berkowitz, Pat Devlin, Mathias Schacht

Research output: Contribution to journalArticlepeer-review

Abstract

In this note we study the emergence of Hamiltonian Berge cycles in random r-uniform hypergraphs. For <![CDATA[ $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.

Original languageEnglish
JournalCombinatorics Probability and Computing
DOIs
StateAccepted/In press - 2020

Keywords

  • 05C20
  • 05C38
  • 05C45
  • 05C65
  • 05C80
  • 05D40
  • 2020 MSC Codes:

Fingerprint

Dive into the research topics of 'Hamiltonian Berge cycles in random hypergraphs'. Together they form a unique fingerprint.

Cite this