Counting multiple graphs in generalized Turán problems

Abstract

We are given graphs $H_1,\dots ,H_k$ and $F$. Consider an $F$-free graph $G$ on $n$ vertices. What is the largest sum of the number of copies of $H_i$? The case $k=1$ has attracted a lot of attention. We also consider a colored variant, where the edges of $G$ are colored with $k$ colors. What is the largest sum of the number of copies of $H_i$ in color $i$? Our motivation to study this colored variant is a recent result stating that the Turán number of the $r$-uniform Berge-$F$ hypergraphs is at most the quantity defined above for $k=2$, $H_1=K_r$ and $H_2=K_2$. In addition to studying these new questions, we obtain new results for generalized Turán problems and also for Berge hypergraphs.

23 pages

References in corpus (2)

• Counting copies of a fixed subgraph in $F$-free graphs
• Avoiding long Berge cycles II, exact bounds for all $n$