Turán problems for linear forests and cliques

Abstract

Given a graph $T$ and a family of graphs $\mathcal{H}$. The generalized Turán number of $\mathcal{H}$ is the maximum number of copies of $T$ in an $\mathcal{H}$-free graph on $n$ vertices, denoted by $ex(n,T,\mathcal{H})$. Let $ex(n,T,\mathcal{H})$ denote the maximum number of copies of $T$ in an $n$-vertex $\mathcal{H}$-free graph. Recently, Alon and Frankl (arXiv2210.15076) determined the exact values of $\mathrm{ex}(\mathrm{n},\{{\mathrm{K}}_{\mathrm{r}+1},{\mathrm{M}}_{\mathrm{s}+1}\})$, where $K_{r+1}$ and $M_{s+1}$ are complete graph on $r+1$ vertices and matching of size $s+1$, respectively. Ma and Hou (arXiv2301.05625) gave the generalized version of Alon and Frankl's Theorem, which determine the exact values of $ex(n,K_r,\{K_{k+1},M_{s+1}\})$. Zhang determined the exact values of $ex(n,K_r,{\mathcal{L}}_{n,s})$, where ${\mathcal{L}}_{n,s}$ be the family of all linear forests of order $n$ with $s$ edges. Inspired by the work of Zhang and Ma, in this paper, we determined the exact number of $ex(n,\{K_{r+1},{\mathcal{L}}_{n,s}\})$.

8 pages