The maximum number of cliques in graphs without large matchings

Jian Wang

Published 2018-12-05Version 1

Given two graphs $T$ and $F$, the maximum number of copies of $T$ in an $F$-free graph on $n$ vertices is denoted by $ex(n,T,F)$ and is called the Generalized Tur\'{a}n number. When $T=K_2$, it reduces to the classical Tur\'{a}n number $ex(n,F)$. In 1961, Erd\H{o}s and Gallai proved that \[ ex(n,M_{k+1})=\max\left\{\binom{2k+1}{2}, \binom{k}{2}+k(n-k)\right\}, \] where $M_{k+1}$ is a matching of size $k+1$. In this note, we prove that for any $s\geq 2$, \[ ex(n,K_s,M_{k+1})=\max\left\{\binom{2k+1}{s}, \binom{k}{s}+(n-k)\binom{k}{s-1}\right\}. \]