Generalized Turan number with given size

Abstract

Generalized Turán problem with given size, denoted as $\mathrm{mex}(m,K_r,F)$, determines the maximum number of $K_r$-copies in an $F$-free graph with $m$ edges. We prove that for $r\ge 3$ and $\hat{I}\pm \in (\frac{2}{r},1]$, any graph $G$ with $m$ edges and $\hat{I}\text{c◯}(m^{\frac{\hat{I}\pm r}{2}})$ $K_r$-copies has a subgraph of order $n_0=\hat{I}\text{c◯}(m^{\frac{\hat{I}}{\pm }}2)$, which contains $\hat{I}\text{c◯}(n_0^{\frac{i(r-2)\hat{I}\pm }{(2-\hat{I}\pm )r-2}})$ $K_i$-copies for each $i=2,\dots ,r$. This implies an upper bound of $\mathrm{mex}(m,K_r,F)$ when an upper bound of $\mathrm{ex}(n,K_r,F)$ is known. Furthermore, we establish an improved upper bound of $\mathrm{mex}(m,K_r,F)$ by $\mathrm{ex}(n,F)$ and ${\min }_{v_0\in V(F)}\mathrm{ex}(n,K_r,F-v_0)$. As a corollary, we show $\mathrm{mex}(m,K_r,K_{s,t})=\hat{I}˜(m^{\frac{rs-\left(\genfrac{}{}{0ex}{}{r}{2}\right)}{2s-1}})$ for $r\ge 3$, $s\ge 2r-2$ and $t\ge (s-1)!+1$, and obtain non-trivial bounds for other graph classes such as complete $r$-partite graphs and $K_s\vee C_{\ell }$, etc.

18 pages