Tight Hamilton cycles in random hypergraphs
classification
🧮 math.CO
keywords
cycleshamiltonrandomtightmethodomegaalgorithmicalgorithms
read the original abstract
We give an algorithmic proof for the existence of tight Hamilton cycles in a random r-uniform hypergraph with edge probability p=n^{-1+eps} for every eps>0. This partly answers a question of Dudek and Frieze [Random Structures Algorithms], who used a second moment method to show that tight Hamilton cycles exist even for p=omega(n)/n (r>2) where omega(n) tends to infinity arbitrary slowly, and for p=(e+o(1))/n (r>3). The method we develop for proving our result applies to related problems as well.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.