Edge‐disjoint Hamilton cycles in random graphs1. Issue 3 (2nd July 2013) - Knox, Fiachra; Kühn, Daniela; Osthus, Deryk
Abstract We show that provided <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82pdsk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />log50n/n≤p≤1−n−1/4log9n</alternatives> we can with high probability find a collection of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82pf3q" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />⌊δ(G)/2⌋</alternatives> edge‐disjoint Hamilton cycles in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82pf26" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G∼Gn, p</alternatives>, plus an additional edge‐disjoint matching of size <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82pf1p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />⌊n/2⌋</alternatives> if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjb82pdxn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />δ(G)</alternatives> is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 397–445, 2015