Combinatorial Theory

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

Mathematics Subject Classifications: 05C80, 05C35

Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience