2019/12/31 by Elad Aigner‐Horev, Aigner-Horev, Elad, Oran Danon +5 · 1 citation
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1912.13512
openalex publication_date 2019/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For two graphs G and H, write G \stackrelrbw\longrightarrow H if G has the property that every \sl proper colouring of its edges yields a \sl rainbow copy of H. We study the thresholds for such so-called \sl anti-Ramsey properties in randomly perturbed dense graphs, which are unions of the form G ∪ \mathbbG(n,p), where G is an n-vertex graph with edge-density at least d, and d is a constant that does not depend on n. Our results in this paper, combined with our results in a companion paper, determine the threshold for the property G ∪ \mathbbG(n,p) \stackrelrbw\longrightarrow Ks for every s. In this paper, we show that for s ≥ 9 the threshold is n^-1/m2(K\lceil s/2 \rceil); in fact, our 1-statement is a supersaturation result. This turns out to (almost) be the threshold for s=8 as well, but for every 4 ≤ s ≤ 7, the threshold is lower; see our companion paper for more details. In this paper, we also consider the property G ∪ \mathbbG(n,p) \stackrelrbw\longrightarrow C2ℓ - 1, and show that the threshold for this property is n-2 for every ℓ ≥ 2; in particular, it does not depend on the length of the cycle C2ℓ - 1. It is worth mentioning that for even cycles, or more generally for any fixed bipartite graph, no random edges are needed at all.