Hamiltonian Berge cycles in random hypergraphs
Combinatorics, Probability and Computing · 2021-03 · 30 (2) · 228-238
DOI: 10.1017/s0963548320000437 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorics, Probability and Computing, online erschienen am 08.09.2020. Verfasst von Deepak Bal und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 20 Literaturangaben.
Abstract (Originalsprache)
In this note we study the emergence of Hamiltonian Berge cycles in random r -uniform hypergraphs. For $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.
Zitieren
APA
Bal, D., Berkowitz, R., Devlin, P., & Schacht, M. (2021). Hamiltonian Berge cycles in random hypergraphs. Combinatorics, Probability and Computing, 30(2), 228-238. https://doi.org/10.1017/s0963548320000437
Vancouver
Bal D, Berkowitz R, Devlin P, Schacht M. Hamiltonian Berge cycles in random hypergraphs. Combinatorics, Probability and Computing. 2021;30(2):228-238. doi:10.1017/s0963548320000437
BibTeX
@article{Bal2021,
author = {Bal, Deepak and Berkowitz, Ross and Devlin, Pat and Schacht, Mathias},
title = {Hamiltonian Berge cycles in random hypergraphs},
journal = {Combinatorics, Probability and Computing},
year = {2021},
volume = {30},
number = {2},
pages = {228--238},
doi = {10.1017/s0963548320000437}
}
EUVIMED