Counting cliques with prescribed intersection sizes

Abstract

We study the generalized Turán problem regarding cliques with restricted intersections, which highlights the motivation from extremal set theory. Let $L=\{{\ell }_1,\dots ,{\ell }_s\}\subset [0,r-1]$ be a fixed integer set with $|L|\notin \{1,r\}$ and ${\ell }_1<\cdots <{\ell }_s$, and let $\hat{I}{¨}_r(n,L)$ denote the maximum number of $r$-cliques in an $n$-vertex graph whose $r$-cliques are $L$-intersecting as a family of $r$-subsets. Helliar and Liu recently initiated the systematic study of the function $\hat{I}{¨}_r(n,L)$ and showed that $\hat{I}{¨}_r(n,L)\le \left(1-\frac{1}{3r}\right){\prod }_{\ell \in L}\frac{n-\ell }{r-\ell }$ for large $n$, improving the trivial bound from the Deza--Erdős--Frankl theorem by a factor of $1-\frac{1}{3r}$. In this article, we improve their result by showing that as $n$ goes to infinity $\hat{I}{¨}_r(n,L)=\hat{I}{˜}_{r,L}(n^{|L|})$ if and only if ${\ell }_1,\dots ,{\ell }_s,r$ form an arithmetic progression and fully determining the corresponding exact values of $\hat{I}{¨}_r(n,L)$ for sufficiently large $n$ in this case. Moreover, when $L=[t,r-1]$, for the generalized Turán extension of the Erdős--Ko--Rado theorem given by Helliar and Liu, we show a Hilton--Milner-type stability result.