2014/10/13 by Deepak Bal, Bal, Deepak, Patrick Bennett +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1410.3405
arxiv created 2014/10/13 · arxiv updated 2014/10/14
We consider the Erdős-Rényi random graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let G(n,m) be a graph with m edges obtained after m steps of this process. Each edge ei (i=1,2,..., m) of G(n,m) independently chooses precisely k ∈ ℕ colours, uniformly at random, from a given set of n-1 colours (one may view ei as a multi-edge). We stop the process prematurely at time M when the following two events hold: G(n,M) is connected and every colour occurs at least once (M=n \choose 2 if some colour does not occur before all edges are present; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether G(n,M) has a rainbow spanning tree (that is, multicoloured tree on n vertices). Clearly, both properties are necessary for the desired tree to exist. In 1994, Frieze and McKay investigated the case k=1 and the answer to this question is "yes" (asymptotically almost surely). However, since the sharp threshold for connectivity is \frac n2 log n and the sharp threshold for seeing all the colours is (n)/(k) log n, the case k=2 is of special importance as in this case the two processes keep up with one another. In this paper, we show that asymptotically almost surely the answer is "yes" also for k ≥ 2.