LARGE RAINBOW CLIQUES IN RANDOMLY PERTURBED DENSE GRAPHS.

For two graphs G and H, write G rbw \rightarrow H if G has the property that every proper coloring 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 \cup G(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 \cup G(n, p) rbw \rightarrow Ks for every s. In this paper, we show that for s \geq 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 \leq s \leq 7, the threshold is lower; see our companion paper for more details. Also in this paper, we determine that the threshold for the property G \cup G(n, p) rbw \rightarrow C2\ell 1 is n 2 for every \ell \geq 2; in particular, the threshold does not depend on the length of the cycle C2\ell 1. For even cycles, and in fact any fixed bipartite graph, no random edges are needed at all; that is, G rbw \rightarrow H always holds, whenever G is as above and H is bipartite. [ABSTRACT FROM AUTHOR]