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 -