TY - JOUR
T1 - Hamiltonian Berge cycles in random hypergraphs
AU - Bal, Deepak
AU - Berkowitz, Ross
AU - Devlin, Pat
AU - Schacht, Mathias
N1 - Publisher Copyright:
© The Author(s), 2020. Published by Cambridge University Press.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2021/3
Y1 - 2021/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85095691264&partnerID=8YFLogxK
U2 - 10.1017/S0963548320000437
DO - 10.1017/S0963548320000437
M3 - Article
AN - SCOPUS:85095691264
SN - 0963-5483
VL - 30
SP - 228
EP - 238
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
IS - 2
ER -