Rainbow trees in uniformly edge‐colored graphs. Issue 2 (17th June 2022)

• Record Type: Journal Article
• Authors: Aigner‐Horev, Elad; Hefetz, Dan; Lahiri, Abhiruk
• Is Part Of: Random structures & algorithms. Volume 62:Issue 2(2023)
• Page Start: 287
• Page End: 303
• Publication Date: 2022-06-17
• Subjects: edge‐coloring -- rainbow trees -- random graphs -- random perturbation; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21103
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We obtain sufficient conditions for the emergence of spanning and almost‐spanning bounded‐degree rainbow trees in various host graphs, having their edges colored independently and uniformly at random, using a predetermined palette. Our first result asserts that a uniform coloring of 𝔾 ( n, ω ( 1 ) / n ), using a palette of size n $$ n $$, a.a.s. admits a rainbow copy of any given bounded‐degree tree on at most ( 1 − ε ) n $$ \left(1-\varepsilon \right)n $$ vertices, where ε > 0 $$ \varepsilon >0 $$ is arbitrarily small yet fixed. This serves as a rainbow variant of a classical result by Alon et al. pertaining to the embedding of bounded‐degree almost‐spanning prescribed trees in 𝔾 ( n, C / n ), where C > 0 $$ C>0 $$ is independent of n $$ n $$ . Given an n $$ n $$ ‐vertex graph G $$ G $$ with minimum degree at least δ n $$ \delta n $$, where δ > 0 $$ \delta >0 $$ is fixed, we use our aforementioned result in order to prove that a uniform coloring of the randomly perturbed graph G ∪ 𝔾 ( n, ω ( 1 ) / n ), using ( 1 + α ) n $$ \left(1+\alpha \right)n $$ colors, where α > 0 $$ \alpha >0 $$ is arbitrarily small yet fixed, a.a.s. admits a rainbow copy of any given bounded‐degree spanning tree. This can be viewed as a rainbow variant of a result by Krivelevich et al. who proved that G ∪ 𝔾 ( n, C / n ), where C > 0 $$ C>0 $$ is independent of n $$ n $$, a.a.s. admits a copy of any given bounded‐degree spanning tree. Finally, and with G $$ G $$ as above, we prove that a uniform coloring of G ∪ 𝔾 ( n, ω ( n − 2 ) ) using n − 1 $$ n-1 $$ colors 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.