Power of k choices and rainbow spanning trees in random graphs

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

m a t h c a l 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

f r a c n 2 l o g n

and the sharp threshold for seeing all the colours is

f r a c n k l o g 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 g e 2

.

Review text

Summary: 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 \(\mathcal{G}(n,m)\) be a graph with \(m\) edges obtained after \(m\) steps of this process. Each edge \(e_i\) (\(i=1,2,\dots, m\)) of \(\mathcal{G}(n,m)\) independently chooses precisely \(k \in\mathbb{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: \(\mathcal{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 \(\mathcal{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. { } \textit{A. Frieze} and \textit{B. D. Mckay} [Random Struct. Algorithms 5, No. 1, 45--56 (1994; Zbl 0796.05084)] 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 {n}{2} \log n\) and the sharp threshold for seeing all the colours is \(\frac{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 \geq 2\).

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Power of \(k\) choices and rainbow spanning trees in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256126)