Small rainbow cliques in randomly perturbed dense graphs. (March 2022)

• Record Type: Journal Article
• Authors: Aigner-Horev, Elad; Danon, Oran; Hefetz, Dan; Letzter, Shoham
• Is Part Of: European journal of combinatorics. Volume 101(2022)
• Publication Date: 2022-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103452
• Languages: English
• ISSNs: 0195-6698

Abstract

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.