Name
Abstract | ||
|---|---|---|
We consider the Erdos-Renyi 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 in edges obtained after in steps of this process. Each edge e(i) (i = 1, 2,..., m) of g(n, m) independently chooses precisely k is an element of N colours, uniformly at random, from a given set of n - 1 colours (one may view e(i) 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)(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 n/2 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. |
Year | Venue | Field |
|---|---|---|
2015 | ELECTRONIC JOURNAL OF COMBINATORICS | Discrete mathematics,Graph,Combinatorics,Random graph,Vertex (geometry),Stochastic process,Spanning tree,Almost surely,Rainbow,Mathematics |
DocType | Volume | Issue |
Journal | 22.0 | 1.0 |
ISSN | Citations | PageRank |
1077-8926 | 1 | 0.41 |
References | Authors | |
6 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deepak Bal | 1 | 35 | 7.32 |
| Patrick Bennett | 2 | 5 | 1.89 |
| Alan M. Frieze | 3 | 4837 | 787.00 |
| Pawel Pralat | 4 | 234 | 48.16 |