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 (12+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.
Mathematics Subject Classifications: 05C80, 05C35
Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience
Cookie SettingseScholarship uses cookies to ensure you have the best experience on our website. You can manage which cookies you want us to use.Our Privacy Statement includes more details on the cookies we use and how we protect your privacy.