Rainbow Hamilton cycles in random graphs

Details Rainbow Hamilton cycles in random graphs Rainbow Hamilton cycles in random graphs

2010-12-31

arxiv.org/abs/1101.0182v1

Mathematics

Combinatorics

26 pages, 4 figures

Scientific paper

One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erdos-Renyi 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 further property that all edges are distinctly colored (rainbow).

Affiliated with

Also associated with

No associations

Rating

Rainbow Hamilton cycles in random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rainbow Hamilton cycles in random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow Hamilton cycles in random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-295147