Tight Hamilton cycles in random hypergraphs. Issue 3 (16th October 2013) - Allen, Peter; Böttcher, Julia; Kohayakawa, Yoshiharu; Person, Yury
Abstract We give an algorithmic proof for the existence of tight Hamilton cycles in a random r‐uniform hypergraph with edge probability <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82hr1s" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=n−1+ε</alternatives> for every <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82hr29" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ε>0</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82hqw7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=ω(n)/n (r≥3)</alternatives> where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82hqz8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ω(n)→∞</alternatives> arbitrary slowly, and for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82hqsp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=(e+o(1))/n (r≥4)</alternatives>. 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