Abstract
In this note we study the emergence of Hamiltonian Berge cycles in random r-uniform hypergraphs. For 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 language | English |
|---|---|
| Pages (from-to) | 228-238 |
| Number of pages | 11 |
| Journal | Combinatorics Probability and Computing |
| Volume | 30 |
| Issue number | 2 |
| DOIs | |
| State | Published - Mar 2021 |
Fingerprint
Dive into the research topics of 'Hamiltonian Berge cycles in random hypergraphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver