Hamiltonian Berge cycles in random hypergraphs

Link:
Autor/in:
Erscheinungsjahr:
2021
Medientyp:
Text
Schlagworte:
  • Hamilton Cycle
  • Random Graphs
  • Degree Sequence
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • Hamilton Cycle
  • Random Graphs
  • Degree Sequence
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/7d51ec20-208e-41ba-94a8-8cef66b6a662