Small rainbow cliques in randomly perturbed dense graphs. (March 2022) - Aigner-Horev, Elad; Danon, Oran; Hefetz, Dan; Letzter, Shoham
Abstract: For two graphs G and H, write G ⟶ rbw H if G has the property that every proper colouring of its edges yields a rainbow copy of H . We study the thresholds for such so-called anti-Ramsey properties in randomly perturbed dense graphs, which are unions of the form G ∪ G ( n, p ), where G is an n -vertex graph with edge-density at least d > 0, and d is independent of n . In a companion paper, we proved that the threshold for the property G ∪ G ( n, p ) ⟶ rbw K ℓ is n − 1 / m 2 ( K ℓ / 2 ), whenever ℓ ≥ 9 . For smaller ℓ, the thresholds behave more erratically, and for 4 ≤ ℓ ≤ 7 they deviate downwards significantly from the aforementioned aesthetic form capturing the thresholds for large cliques. In particular, we show that the thresholds for ℓ ∈ 4, 5, 7 are n − 5 / 4, n − 1, and n − 7 / 15, respectively. For ℓ ∈ 6, 8 we determine the threshold up to a ( 1 + o ( 1 ) ) -factor in the exponent: they are n − ( 2 / 3 + o ( 1 ) ) and n − ( 2 / 5 + o ( 1 ) ), respectively. For ℓ = 3, the threshold is n − 2 ; this follows from a more general result about odd cycles in our companion paper.