0
$\begingroup$

Thinking of an edge as of a $2$-clique, it's natural to consider a slightly more general question than Turan considered in his celebrated theorem: given $r \le k \le n$, what is the maximal possible number of $r$-cliques in a graph $X$ on $n$ vertices without $k$-cliques? Has this question been considered in the literature?

Yet more generally, given two graphs $G$ and $H$ and a number $n$, one could ask for the maximum of the homomorphism number $hom(G,X)$ over all graphs $X$ on $n$ vertices satisfying $hom(H,X)=0$. Any references for this one maybe?

Improve this question
$\endgroup$
2
  • $\begingroup$ The opposite question, about the minimum number of $r$-cliques in a graph without $k$-independent sets (which is basically equivalent for $r=2$) was asked by Erdős in 1962. A reference to some results as well as discussion of prior work is contained in Minimum Number of k-Cliques in Graphs with Bounded Independence Number by Oleg Pikhurko and Emil R. Vaughan in Combinatorics, Probability, and Computing doi.org/10.1007/BF00279952 $\endgroup$
    – Will Sawin
    Commented Sep 14, 2021 at 16:17
  • $\begingroup$ The first question was answered by Zykov; see users.monash.edu.au/~davidwo/papers/Wood-GC07.pdf $\endgroup$
    – David Wood
    Commented Sep 15, 2021 at 10:11

1 Answer 1

Reset to default
2
$\begingroup$

The first question was studied by Moon and Moser. You could read a proof of Turán's theorem using this idea in the article by Aigner (it is the third proof).

Even more general questions have been studied: what are the inequalities that are satisfied by the number of homomorphisms from a collection $H_1,\dotsc,H_k$ of graphs. The general problem is known to be undecidable, thanks to Hatami and Norine, but it has not stopped people from proving many results of this kind.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .