2023/10/27 by Katsamaktsis, Kyriakos, Letzter, Shoham, Sgueglia, Amedeo · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.18284
For a given δ∈ (0,1), the randomly perturbed graph model is defined as the union of any n-vertex graph G0 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 C if each edge is coloured independently and uniformly at random with a colour from 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 δ∈ (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 G0 be an n-vertex graph with δ(G0)≥ δn. Then a uniformly coloured G0 ∪ 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).