Rainbow subgraphs of uniformly coloured randomly perturbed graphs

Abstract

For a given $\delta \in (0,1)$, the randomly perturbed graph model is defined as the union of any $n$-vertex graph $G_0$ with minimum degree $\delta n$ and the binomial random graph $\mathbf{G}(n,p)$ on the same vertex set. Moreover, we say that a graph is uniformly coloured with colours in $\mathcal{C}$ if each edge is coloured independently and uniformly at random with a colour from $\mathcal{C}$. Based on a coupling idea of McDiarmird, we provide a general tool to tackle problems concerning finding a rainbow copy of a graph $H=H(n)$ in a uniformly coloured perturbed $n$-vertex graph with colours in $[(1+o(1))e(H)]$. For example, our machinery easily allows to recover a result of Aigner-Horev and Hefetz concerning rainbow Hamilton cycles, and to improve a result of Aigner-Horev, Hefetz and Lahiri concerning rainbow bounded-degree spanning trees. Furthermore, using different methods, we prove that for any $\delta \in (0,1)$ and integer $d\ge 2$, there exists $C=C(\delta ,d)>0$ such that the following holds. Let $T$ be a tree on $n$ vertices with maximum degree at most $d$ and $G_0$ be an $n$-vertex graph with $\delta (G_0)\ge \delta n$. Then a uniformly coloured $G_0\cup \mathbf{G}(n,C/n)$ with colours in $[n-1]$ contains a rainbow copy of $T$ with high probability. This is optimal both in terms of colours and edge probability (up to a constant factor).

arXiv comment22 pages, 1 figure; final version as accepted for publication in Innovations in Graph Theory