Power of $k$ Choices and Rainbow Spanning Trees in Random Graphs

摘要

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,ldots, m$) of $mathcal{G}(n,m)$ independently chooses precisely $k inmathbb{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.