Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs

Link:
Autor/in:
Erscheinungsjahr:
2020
Medientyp:
Text
Beschreibung:
  • For positive integers r>, an r‐uniform hypergraph is called an ‐cycle if there exists a cyclic ordering of its vertices such that each of its edges consists of r consecutive vertices, and such that every pair of consecutive edges (in the natural ordering of the edges) intersect in precisely vertices; such cycles are said to be linear when =1, and nonlinear when >1. We determine the sharp threshold for nonlinear Hamiltonian cycles and show that for all r>>1, the threshold for the appearance of a Hamiltonian ‐cycle in the random r‐uniform hypergraph on n vertices is sharp and given by for an explicitly specified function λ. This resolves several questions raised by Dudek and Frieze in 2011.10
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/76f19ea5-f2cc-4add-a196-3aea0db22e35