Rainbow spanning trees in random subgraphs of dense regular graphs

Abstract

We consider the following random model for edge-colored graphs. A graph $G$ on $n$ vertices is fixed, and a random subgraph $G_p$ is chosen by letting each edge of $G$ remain independently with probability $p$. Then, each edge of $G_p$ is colored uniformly at random from the set $[n-1]$. A result of Frieze and McKay (Random Structures and Algorithms, 1994) implies that when $G=K_n$ and $p=(2+\epsilon )\frac{\log n}{n}$ for some constant $\epsilon >0$, then $G_p$ almost surely contains a rainbow spanning tree. In this paper, we show that if $G$ is a $d$-regular $\Omega (n)$-edge-connected graph, then when $p=(2+\epsilon )\frac{\log n}{d}$ for some constant $\epsilon >0$, $G_p$ almost surely contains a rainbow spanning tree. Our main tool is a new edge-replacement method for rainbow forests.

arXiv comment11 pages, 1 figure