Giant Rainbow Trees in Sparse Random Graphs

Abstract

For any small constant $\epsilon >0$, the Erdős-Rényi random graph $G(n,\frac{1+\epsilon }{n})$ with high probability has a unique largest component which contains $(1\pm O(\epsilon ))2\epsilon n$ vertices. Let $G_c(n,p)$ be obtained by assigning each edge in $G(n,p)$ a color in $[c]$ independently and uniformly. Cooley, Do, Erde, and Missethan proved that for any fixed $\alpha >0$, $G_{\alpha n}(n,\frac{1+\epsilon }{n})$ with high probability contains a rainbow tree (a tree that does not repeat colors) which covers $(1\pm O(\epsilon ))\frac{\alpha }{\alpha +1}\epsilon n$ vertices, and conjectured that there is one which covers $(1\pm O(\epsilon ))2\epsilon n$. In this paper, we achieve the correct leading constant and prove their conjecture correct up to a logarithmic factor in the error term, as we show that with high probability $G_{\alpha n}(n,\frac{1+\epsilon }{n})$ contains a rainbow tree which covers $(1\pm O(\epsilon \log (1/\epsilon )))2\epsilon n$ vertices.

9 pages