Giant rainbow trees in sparse random graphs

For any small constant ϵ > 0 , the Erdős-Rényi random graph G ( n , 1 + ϵ n ) with high probability has a unique largest component which contains ( 1 ± O ( ϵ ) ) 2 ϵ 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 α > 0 , G α n ( n , 1 + ϵ n ) with high probability contains a rainbow tree (a tree that does not repeat colors) which covers ( 1 ± O ( ϵ ) ) α α + 1 ϵ n vertices, and conjectured that there is one which covers ( 1 ± O ( ϵ ) ) 2 ϵ 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 α n ( n , 1 + ϵ n ) contains a rainbow tree which covers ( 1 ± O ( ϵ log ( 1 / ϵ ) ) ) 2 ϵ n vertices.