Rainbow subgraphs of uniformly coloured randomly perturbed graphs

For a given <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , the randomly perturbed graph model is defined as the union of any <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -vertex graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>G</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> with minimum degree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> and the binomial random graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi mathvariant="bold">G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>p</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> on the same vertex set. Moreover, we say that a graph is uniformly coloured with colours in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>𝒞</mml:mi> </mml:math> if each edge is coloured independently and uniformly at random with a colour from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>𝒞</mml:mi> </mml:math> . Based on a coupling idea of McDiarmid, we provide a general tool to tackle problems concerning finding a rainbow copy of a graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo>=</mml:mo> <mml:mi>H</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> in a uniformly coloured perturbed <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -vertex graph with colours in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>[</mml:mo> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mi>e</mml:mi> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and integer <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , there exists <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>=</mml:mo> <mml:mi>C</mml:mi> <mml:mo>(</mml:mo> <mml:mi>δ</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> <mml:mo>)</mml:mo> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> such that the following holds. Let <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> be a tree on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> vertices with maximum degree at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>d</mml:mi> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>G</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> be an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -vertex graph with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>G</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo>)</mml:mo> <mml:mo>≥</mml:mo> <mml:mi>δ</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> . Then a uniformly coloured <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>G</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo>∪</mml:mo> <mml:mi mathvariant="bold">G</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>C</mml:mi> <mml:mo>/</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> with colours in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> contains a rainbow copy of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> with high probability. This is optimal both in terms of colours and edge probability (up to a constant factor).