Rainbow Tur\'an number of even cycles, repeated patterns and blow-ups of cycles

2020 
The rainbow Turan number $\mathrm{ex}^*(n,H)$ of a graph $H$ is the maximum possible number of edges in a properly edge-coloured $n$-vertex graph with no rainbow subgraph isomorphic to $H$. We prove that for any integer $k\geq 2$, $\mathrm{ex}^*(n,C_{2k})=O(n^{1+1/k})$. This is tight and establishes a conjecture of Keevash, Mubayi, Sudakov and Verstraete. We use the same method to prove several other conjectures in various topics. First, we prove that there exists a constant $c$ such that any properly edge-coloured $n$-vertex graph with more than $cn(\log n)^4$ edges contains a rainbow cycle. It is known that there exist properly edge-coloured $n$-vertex graphs with $\Omega(n\log n)$ edges which do not contain any rainbow cycle. Secondly, we prove that in any proper edge-colouring of $K_n$ with $o(n^{\frac{r}{r-1}\cdot \frac{k-1}{k}})$ colours, there exist $r$ colour-isomorphic, pairwise vertex-disjoint copies of $C_{2k}$. This proves in a strong form a conjecture of Conlon and Tyomkyn, and a strenghtened version proposed by Xu, Zhang, Jing and Ge. Finally, we answer a question of Jiang and Newman by showing that there exists a constant $c=c(r)$ such that any $n$-vertex graph with more than $cn^{2-1/r}(\log n)^{7/r}$ edges contains the $r$-blowup of an even cycle.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    23
    References
    7
    Citations
    NaN
    KQI
    []