Large rainbow cliques in randomly perturbed dense graphs

Abstract

For two graphs $G$ and $H$, write $G\stackrel{\mathrm{rbw}}{⟶}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\cup \mathbb{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 \mathbb{G}(n,p)\stackrel{\mathrm{rbw}}{⟶}{K}_s$ for every $s$. In this paper, we show that for $s\ge 9$ the threshold is $n^{-1/m_2(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\le s\le 7$, the threshold is lower; see our companion paper for more details. In this paper, we also consider the property $G\cup \mathbb{G}(n,p)\stackrel{\mathrm{rbw}}{⟶}{C}_{2\ell -1}$, and show that the threshold for this property is $n^{-2}$ for every $\ell \ge 2$; in particular, it does not depend on the length of the cycle $C_{2\ell -1}$. It is worth mentioning that for even cycles, or more generally for any fixed bipartite graph, no random edges are needed at all.

This is the journal version