Rainbow subgraphs of uniformly coloured randomly perturbed graphs

For a given δ ∈ ( 0 , 1 ) , the randomly perturbed graph model is defined as the union of any n -vertex graph G 0 with minimum degree δ n and the binomial random graph G ( n , p ) on the same vertex set. Moreover, we say that a graph is uniformly coloured with colours in 𝒞 if each edge is coloured independently and uniformly at random with a colour from 𝒞 . Based on a coupling idea of McDiarmid, 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 δ ∈ ( 0 , 1 ) and integer d ≥ 2 , there exists C = C ( δ , 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 δ ( G 0 ) ≥ δ n . Then a uniformly coloured G 0 ∪ 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).