Hamiltonian Berge cycles in random hypergraphs

DOI10.1017/S0963548320000437MaRDI QIDQ4993259zbMATH OpenOpenAlexFDO

Authors Deepak Bal, Ross Berkowitz, Pat Devlin, M. Schacht

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.03596

zbMATH Keywords

Berge HamiltonicityErdős-Rényi random \(r\)-graphweak Berge cycles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this note, we study the emergence of Hamiltonian Berge cycles in random $r$-uniform hypergraphs. For $rgeq3$, we prove an optimal stopping-time result that if edges are sequently added to an initially empty $r$-graph, then as soon as the minimum degree is at least 2, the hypergraph almost surely has such a cycle. In particular, this determines the threshold probability for Berge Hamiltonicity of the ErdH{o}s--R'enyi random $r$-graph, and we also show that the $2$-out random $r$-graph almost surely has such a cycle. We obtain similar results for extit{weak Berge} cycles as well, thus resolving a conjecture of Poole.

Recommendations

• A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Tight Hamilton cycles in random uniform hypergraphs
• Tight Hamilton cycles in random hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs

Cites work

• A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs
• Hamilton cycles in 3-out
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 1496581 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• Introduction to Random Graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Long paths and Hamiltonicity in random graphs
• Loose Hamilton cycles in random uniform hypergraphs
• On offset Hamilton cycles in random hypergraphs
• On the connectivity of random m-orientable graphs and digraphs
• Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
• Perfect fractional matchings in \(k\)-out hypergraphs
• Random graph's Hamiltonicity is strongly tied to its minimum degree
• Random graphs.
• Spanning structures and universality in sparse hypergraphs
• Tight Hamilton cycles in random uniform hypergraphs

Cited in

(7)

• On Hamiltonian Berge cycles in [3]-uniform hypergraphs
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Monochromatic Hamiltonian Berge-cycles in colored hypergraphs
• Monochromatic Hamiltoniant-tight Berge-cycles in hypergraphs
• A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs
• What Are Higher-Order Networks?
• Hamilton cycles in the line graph of a random hypergraph

This page was built for publication: Hamiltonian Berge cycles in random hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993259)