Maximum packings in graphs forbidding given rainbow cycles

Abstract

For graphs $F$ and $G$, $F$-multicolor Turán number of $G$, denoted by ${\mathrm{ex}}_F(n,G)$, is the maximum number of edge-disjoint copies of $F$ in an $n$-vertex graph such that there is no copy of $G$ whose edges come from distinct copies of $F$. We study this parameter mainly for cycle pairs and determine, up to asymptotic order, when ${\mathrm{ex}}_{C_k}(n,C_{\ell })$ attains the three natural thresholds: the upper bound, the lower bound, and the $n^{2-o(1)}$ regime. In particular, for every odd $k\ge 5$ and every $t\ge 1$, where $C_k(t)$ denotes the $t$-blow-up of $C_k$, we prove ${\mathrm{ex}}_{C_k(t)}(n,C_{k-2})=n^2/(kt{)}^2+o(n^2),$ and establish a corresponding stability theorem. We further show that if $F$ and $G$ have the same odd girth $k$ and there exist homomorphisms from both $F$ and $G$ to $C_k$, then ${\mathrm{ex}}_F(n,G)=n^{2-o(1)}$; in particular, ${\mathrm{ex}}_{C_k}(n,C_k)=n^{2-o(1)}$ for odd $k$. In addition, we prove ${\mathrm{ex}}_{C_{2k+1}}(n,C_{2\ell +1})=O\left(n^{1+1/\lceil \ell /k\rceil }\right)$ for $\ell >k$ and ${\mathrm{ex}}_F(n,G)=O(\mathrm{ex}(n,G))$ for bipartite $G$. We particularly establish ${\mathrm{ex}}_{C_4}(n,C_4)=\frac{\sqrt{2}}{8}{n}^{3/2}+O(n)$, and give a sufficient condition under which the lower bound cannot be attained.

28 pages, 5 figures