Rainbow hamilton cycles in random graphs. Issue 3 (13th February 2013)

• Record Type: Journal Article
• Authors: Frieze, Alan; Loh, Po‐Shen
• Is Part Of: Random structures & algorithms. Volume 44:Issue 3(2014)
• Page Start: 328
• Page End: 354
• Publication Date: 2013-02-13
• Subjects: Hamilton cycles -- random graphs -- coloring; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20475
• Languages: English
• ISSNs: 1042-9832

Abstract

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 G n, p is around p ∼ log n + log log n n . 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 G n, p are randomly colored from a set of (1 + o (1)) n colors, with p = ( 1 + o ( 1 ) ) log n n, 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