2021/02/24 by Peter Bradshaw, Bradshaw, Peter
Computer Science · Mathematics · #05C05 #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2102.12012
openalex publication_date 2021/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the following random model for edge-colored graphs. A graph G on n vertices is fixed, and a random subgraph Gp is chosen by letting each edge of G remain independently with probability p. Then, each edge of Gp 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 = Kn and p = (2 + ε) (log n)/(n) for some constant ε> 0, then Gp almost surely contains a rainbow spanning tree. In this paper, we show that if G is a d-regular Ω(n)-edge-connected graph, then when p = (2 + ε) \frac log nd for some constant ε> 0, Gp almost surely contains a rainbow spanning tree. Our main tool is a new edge-replacement method for rainbow forests.