Resilience for tight Hamiltonicity

Abstract

We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any $\gamma >0$ and $k\ge 3$, we show that asymptotically almost surely, every subgraph of the binomial random $k$-uniform hypergraph $G^{(k)}(n,n^{\gamma -1})$ in which all $(k-1)$-sets are contained in at least $(\frac{1}{2}+2\gamma )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.

arXiv comment50 pages, 1 figure

References in corpus (6)

• Hypergraph regularity and the multidimensional Szemerédi theorem
• A relative Szemerédi theorem
• Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs
• Hamilton Cycles in Random Graphs: a bibliography
• Co-degrees resilience for perfect matchings in random hypergraphs
• Regularity inheritance in hypergraphs