Search

In this paper we continue the study of a natural generalisation of Turán's forbidden subgraph problem and the Ruzsa-Szemerédi problem. Let $ex_F(n,G)$ denote the maximum number of edge-disjoint copies of a fixed simple graph $F$ that can be placed on an $n$-vertex ground set without forming a subgraph $G$ whose edges are from different $F$-copies. The case when both $F$ and $G$ are triangles essentially gives back the theorem of Ruzsa and Szemerédi, and we extend their results for the case of arbitrary pairs of cliques by applying a number theoretic result due to Alon and Shapira. We also settle the case when $F$ is a pentagon and $G$ is a triangle and give bounds for longer cycles as well.