A generalization of Turan’s theorem

combinatoricsextremal-combinatoricsextremal-graph-theorygraph theoryhypergraphs

The Turan's theorem gives a tight upper bound of the number of edges in a $K_n$-free graph. I didn't manage to find some information about the generalization of this theorem when we're asked to estimate the number of $K_{m<n}$ in a $K_n$-free graph ($K_{m<n}$ stands for $K_m$ with $m<n$). In particular, I'm interested in the $m=n-1$ case which can be equivalently stated as the question about the maximum number of $\omega(G)$-cliques in a graph $G$. Could you please tell me whether some results were obtained on these two problems?

Hypergraph version. We can formulate the first general question in terms of $m$-uniform hypergraphs, i. e. ask about the maximum size of a family $F$ of $m$-subsets of a set $A$, such that any $n$-subset of $A$ contains a $2$-subset which is not a subset of some set in $F$. Let us denote this property of $F$ as $P$ and consider the special case $m=n-1$ for $n\geq3$. Note that to cover the edges of $K_n$ with $K_{n-1}$ subgraphs it is necessary and sufficient to choose three $K_{n-1}$ subgraphs. This allows to replace $P$ with the union of three distinct sets in $F$ contains at least $n+1$ elements. So for $n\geq3$, our second question may sound as follows:

Let $A$ be a $k$-element set, and $F$ is a family of $(n-1)$-subsets of $A$. Given the unioun of any three sets from $F$ contains at least $n+1$ elements, what is the maximum size of $F$?

Assumption. After thinking a little, I came to the following conclusion. Could it turn out that the Turan $K_n$-free graph contains not only the largest number of $K_2$, but also $K_m$ for all $m<n$?
If this is so, then, considering the decomposition $k=s(n-1)+r$ with $0\leq r<n-1$, we come to the conclusion that the largest number of $K_{m<n}$ graphs in a $k$-vertex $K_n$-free graph is equal to

$$\sum\limits_{\substack{0\leq x\leq n-1-r\\0\leq y\leq r\\x+y=m}}{{n-1-r}\choose{x}}{{r}\choose{y}}s^x(s+1)^y$$

Best Answer

Seems that the assumption in my question is true, and the Turan $T(k,n-1)$ graph maximizes the number of $m$-cliques among $k$-vertex $K_n$-free graphs for all $m<n$ (not only $m=2$). The proof essentially repeats Zykov's symmetrization argument with the degree of a vertex $v$ replaced with the number of $m$-cliques containing $v$. Also, we prove the lemma that $T(k,n-1)$ maximizes the number of $m$-cliques among complete multipartite $K_n$-free graphs on $k$ vertices. Here is a link to the detailed proof in Russian, I will try to translate it into English soon.

Related Question