Resilience for tight Hamiltonicity

Allen, PeterORCID logo; Parczyk, Olaf; and Pfenninger, Vincent (2024) Resilience for tight Hamiltonicity. Combinatorial Theory, 4 (1): #9. ISSN 2766-1334
Copy

We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any γ > 0 and k ≥ 3, we show that asymptotically almost surely, every subgraph of the binomial random k-uniform hypergraph G (k)(n, n γ−1) in which all (k − 1)-sets are contained in at least (1/2 + 2γ) pn edges has a tight Hamilton cycle. This is a cyclic ordering of the n vertices such that each consecutive k vertices forms an edge.

picture_as_pdf

picture_as_pdf
subject
Published Version
Available under Creative Commons: Attribution 4.0

Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads