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

DOI10.1007/S11856-022-2380-9arXiv2006.01062MaRDI QIDQ6341840FDOQ6341840

Authors: Oliver Janzer 

Publication date: 1 June 2020

Abstract: The rainbow Tur'an number $mathrm{ex}^{\ast }(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 $kgeq2$, $mathrm{ex}^{\ast }(n,C_{2k})=O(n^{1+1/k})$. This is tight and establishes a conjecture of Keevash, Mubayi, Sudakov and Verstra"ete. 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(logn{)}^4$ edges contains a rainbow cycle. It is known that there exist properly edge-coloured $n$-vertex graphs with $Omega(nlogn)$ edges which do not contain any rainbow cycle. Secondly, we show that in any proper edge-colouring of $K_n$ with $o(n^{fracrr-1cdotfrack-1k})$ 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. Moreover, 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 $c{n}^{2-1/r}(logn{)}^{7/r}$ edges contains the $r$-blowup of an even cycle. Finally, we prove that the $r$-blowup of $C_{2k}$ has Tur'an number $O(n^{2-frac1r+frac1k+r-1+o(1)})$, which can be used to disprove an old conjecture of ErdH os and Simonovits.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Paths and cycles (05C38) Ramsey theory (05D10)

This page was built for publication: Rainbow Tur\'an number of even cycles, repeated patterns and blow-ups of cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341840)