Tight Hamilton cycles in random hypergraphs

Abstract

We give an algorithmic proof for the existence of tight Hamilton cycles in a random r-uniform hypergraph with edge probability for every . This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374–385), who used a second moment method to show that tight Hamilton cycles exist even for where arbitrary slowly, and for . The method we develop for proving our result applies to related problems as well. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 446–465, 2015

Locations

• arXiv (Cornell University) - View - PDF
• Random Structures and Algorithms - View