2023/08/27 by Tolson Bell, Alan Frieze, Bell, Tolson +1
Mathematics · Computer Science · #Stochastic processes and statistical mechanics #Limits and Structures in Graph Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2308.14141
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 Gc(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(ε))\fracαα+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.