EUVIMEDEUVIMED entdecken
Crossref

Hamiltonian Berge cycles in random hypergraphs

Deepak Bal, Ross Berkowitz, Pat Devlin, Mathias Schacht

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →