Counting copies of a fixed subgraph in $F$-free graphs

Abstract

Fix graphs $F$ and $H$ and let $ex(n,H,F)$ denote the maximum possible number of copies of the graph $H$ in an $n$-vertex $F$-free graph. The systematic study of this function was initiated by Alon and Shikhelman [{\it J. Comb. Theory, B}. {\bf 121} (2016)]. In this paper, we give new general bounds concerning this generalized Turán function. We also determine $ex(n,P_k,K_{2,t})$ (where $P_k$ is a path on $k$ vertices) and $ex(n,C_k,K_{2,t})$ asymptotically for every $k$ and $t$. For example, it is shown that for $t\ge 2$ and $k\ge 5$ we have $ex(n,C_k,K_{2,t})=\left(\frac{1}{2k}+o(1)\right)(t-1{)}^{k/2}{n}^{k/2}$. We also characterize the graphs $F$ that cause the function $ex(n,C_k,F)$ to be linear in $n$. In the final section we discuss a connection between the function $ex(n,H,F)$ and Berge hypergraph problems.

Accepted to European Journal of Combinatorics

References in corpus (1)

• Supersaturation for subgraph counts

Cited by in corpus (12)

• Subgraph densities in a surface
• Tree densities in sparse graph classes
• Maximizing five-cycles in $K_r$-free graphs
• Triangles in graphs without bipartite suspensions
• Counting multiple graphs in generalized Turán problems
• Few $T$ copies in $H$-saturated graphs
• Some extremal results on hypergraph Turán problems
• The generalized Turán number of spanning linear forests
• The Maximum Number of Cliques in Hypergraphs without Large Matchings
• Triangle Ramsey numbers of complete graphs
• On the number of $k$-gons in finite projective planes
• Paths of Length Three are $K_{r+1}$-Turán Good