Some sharp results on the generalized Turán numbers

Abstract

For graphs $T,H$, let $ex(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex $H$-free graph. In this paper we prove some sharp results on this generalization of Turán numbers, where our focus is for the graphs $T,H$ satisfying $\chi (T)<\chi (H)$. This can be dated back to Erdős, where he generalized the celebrated Turán's theorem by showing that for any $r\ge m$, the Turán graph $T_r(n)$ uniquely attains $ex(n,K_m,K_{r+1})$. For general graphs $H$ with $\chi (H)=r+1>m$, Alon and Shikhelman showed that $ex(n,K_m,H)=\left(\genfrac{}{}{0ex}{}{r}{m}\right)(\frac{n}{r}{)}^m+o(n^m)$. Here we determine this error term $o(n^m)$ up to a constant factor. We prove that $ex(n,K_m,H)=\left(\genfrac{}{}{0ex}{}{r}{m}\right)(\frac{n}{r}{)}^m+biex(n,H)\cdot \Theta (n^{m-2})$, where $biex(n,H)$ is the Turán number of the decomposition family of $H$. As a special case, we extend Erdős' result, by showing that $T_r(n)$ uniquely attains $ex(n,K_m,H)$ for any edge-critical graph $H$. We also consider $T$ being non-clique, where even the simplest case seems to be intricate. Following from a more general result, we show that for all $s\le t$, $T_2(n)$ maximizes the number of $K_{s,t}$ in $n$-vertex triangle-free graphs if and only if $t<s+\frac{1}{2}+\sqrt{2s+\frac{1}{4}}$.