The generalised rainbow Turán problem for cycles

Abstract

Given an edge-coloured graph, we say that a subgraph is rainbow if all of its edges have different colours. Let $\mathrm{ex}(n,H,$rainbow-$F)$ denote the maximal number of copies of $H$ that a properly edge-coloured graph on $n$ vertices can contain if it has no rainbow subgraph isomorphic to $F$. We determine the order of magnitude of $\mathrm{ex}(n,C_s,$rainbow-$C_t)$ for all $s,t$ with $s\ne 3$. In particular, we answer a question of Gerbner, Mészáros, Methuku and Palmer by showing that $\mathrm{ex}(n,C_{2k},$rainbow-$C_{2k})$ is $\Theta (n^{k-1})$ if $k\ge 3$ and $\Theta (n^2)$ if $k=2$. We also determine the order of magnitude of $\mathrm{ex}(n,P_{\ell },$rainbow-$C_{2k})$ for all $k,\ell \ge 2$, where $P_{\ell }$ denotes the path with $\ell$ edges.

arXiv comment14 pages