Resilience for tight Hamiltonicity
Allen, Peter
; Parczyk, Olaf; and Pfenninger, Vincent
(2024)
Resilience for tight Hamiltonicity.
Combinatorial Theory, 4 (1): #9.
ISSN 2766-1334
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.
| Item Type | Article |
|---|---|
| Keywords | random graphs,hypergraphs,tight Hamilton cycles,resilience |
| Departments | Mathematics |
| DOI | 10.5070/C64163846 |
| Date Deposited | 12 Jan 2024 14:27 |
| URI | https://researchonline.lse.ac.uk/id/eprint/121362 |
Explore Further
- https://www.lse.ac.uk/Mathematics/people/Peter-Allen (Author)
- http://www.scopus.com/inward/record.url?scp=85198860577&partnerID=8YFLogxK (Scopus publication)
- 10.5070/C64163846 (DOI)
ORCID: https://orcid.org/0000-0001-6555-3501
