2021/05/18 by Aigner-Horev, Elad, Hefetz, Dan, Lahiri, Abhiruk · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2105.08315
We obtain sufficient conditions for the emergence of spanning and almost-spanning bounded-degree \sl rainbow trees in various host graphs, having their edges coloured independently and uniformly at random, using a predetermined palette. Our first result asserts that a uniform colouring of \mathbbG(n,ω(1)/n), using a palette of size n, a.a.s. admits a rainbow copy of any given bounded-degree tree on at most (1-ε)n vertices, where ε > 0 is arbitrarily small yet fixed. This serves as a rainbow variant of a classical result by Alon, Krivelevich, and Sudakov pertaining to the embedding of bounded-degree almost-spanning prescribed trees in \mathbbG(n,C/n), where C > 0 is independent of n. Given an n-vertex graph G with minimum degree at least δn, where δ> 0 is fixed, we use our aforementioned result in order to prove that a uniform colouring of the randomly perturbed graph G ∪ \mathbbG(n,ω(1)/n), using (1+α)n colours, where α> 0 is arbitrarily small yet fixed, a.a.s. admits a rainbow copy of any given bounded-degree \sl spanning tree. This can be viewed as a rainbow variant of a result by Krivelevich, Kwan, and Sudakov who proved that G ∪ \mathbbG(n,C/n), where C > 0 is independent of n, a.a.s. admits a copy of any given bounded-degree spanning tree. Finally, and with G as above, we prove that a uniform colouring of G ∪ \mathbbG(n,ω(n-2)) using n-1 colours a.a.s. admits a rainbow spanning tree. Put another way, the trivial lower bound on the size of the palette required for supporting a rainbow spanning tree is also sufficient, essentially as soon as the random perturbation a.a.s. has edges.