Rainbow hamilton cycles in random graphs. Issue 3 (13th February 2013) - Frieze, Alan; Loh, Po‐Shen
Abstract One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erdős‐Rényi random graph Gn, p is around <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s3g0b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p∼logn+loglognn</alternatives>. Much research has been done to extend this to increasingly challenging random structures. In particular, a recent result by Frieze determined the asymptotic threshold for a loose Hamilton cycle in the random 3‐uniform hypergraph by connecting 3‐uniform hypergraphs to edge‐colored graphs. In this work, we consider that setting of edge‐colored graphs, and prove a result which achieves the best possible first order constant. Specifically, when the edges of Gn, p are randomly colored from a set of (1 + o(1))n colors, with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s3fxq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=(1+o(1))lognn</alternatives>, we show that one can almost always find a Hamilton cycle which has the additional property that all edges are distinctly colored (rainbow).Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 44, 328‐354, 2014