Tight Hamilton cycles in random hypergraphs |
| |
| Authors: | Peter Allen Julia Böttcher Yoshiharu Kohayakawa Yury Person |
| |
| Affiliation: | 1. Department of Mathematics, London School of Economics, London, UK;2. Instituto de Matemática e Estatística, Universidade de S?o Paulo, S?o Paulo, Brazil;3. Goethe‐Universit?t, Institute of Mathematics, Frankfurt, Germany |
| |
| 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 |
| |
| Keywords: | random hypergraphs spanning subgraphs Hamilton cycles algorithms |
|
|
