Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my notes, Turán's Theorem is stated as follows:

Theorem: Let $G$ be a graph on $n$ vertices. Then $e(G) > e(T_{r-1}(n)) \implies G \supset K_r $.

There are then several remarks on the theorem, one of which I don't follow:

Remark: If we knew $G$ was $(r-1)$-partite, then we are done by some kind of AM-GM inequality. But there's no reason why $G$ should be $(r-1)$-partite: e.g. $C_5 $ is $K_3$-free, but not bipartite.

Firstly, am I correct in saying that the reasoning for the above is that if we knew $G$ was $(r-1)$-partite, then it couldn't contain a $K_r$, and so we'd aim to prove (using "some kind of AM-GM inequality") that $e(G) < e(T_{r-1}(n))$? My main problem is that I don't quite know what "some kind of AM-GM inequality" actually means. Could someone show me explicitly what is meant here?

My thoughts: I can sort of see what's going on: we aim to show that the largest number of edges an $(r-1)$-partite graph can have without containing $K_r$ occurs when the vertex classes are as equal in size as possible (as per the definition of Turán's graph). I don't see how AM-GM comes into it though.

Thank you.

share|improve this question

1 Answer 1

Assume that $G$ is $(r-1)$-partite. (You are right in observing that $G$ does not contain $K_r$ as a subgraph.) Let the sizes of the $(r-1)$ vertex classes be $n_1, n_2, \ldots, n_{r-1}$. Then the number of edges is maximised when $G$ is a complete $(r-1)$-partite graph on these vertices.

The number of edges in a complete $(r-1)$-partite graph on these vertices is $$ \frac{n(n-1)}{2} - \sum_{i=1}^{r-1} \frac{n_i (n_i-1)}{2}. $$ (Of the $\frac{n(n-1)}{2}$ edges in a complete graph, we should remove the edges lying inside each of the $(r-1)$ parts.) This can be simplified to $$ \frac{n^2}{2} - \sum_{i=1}^{r-1} \frac{n_i^2}{2} $$ since $\sum_i n_i = n$. Maximizing this quantity is equivalent to minimizing $$ \sum_{i=1}^{r-1} n_i^2 $$ subject to the condition $\sum_i n_i = n$. By Cauchy-Schwarz, we have $$ \begin{align*} (r-1) \cdot \left( \sum_{i=1}^{r-1} n_i^2 \right) &\geqslant \left( \sum_{i=1}^{r-1} n_i \right)^2 \\ &= n^2, \end{align*} $$ with equality when all the $r-1$ numbers $n_1, \ldots, n_{r-1}$ are equal. Since these numbers are integral, we want them to be as equal to each other as possible.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.