In Bondy and Murty's Graph Theory, exercise $1.1.11$ defines something called Turán's graph $T_{k, n}$, as a complete, $k$-partite graph where all parts are of size $\lceil \frac{n}{k} \rceil$, or $\lfloor \frac{n}{k} \rfloor$. I want to show the following:

$T_{k, n}$ has more edges than any other complete $k$-partite graph with $n$ vertices.

I know from part $a)$ that in this case, the number of edges of a complete, $k$-partite graph is $\frac{1}{2} \sum_{i=1}^{k} a_{i}(n-a_{i})$, where $a_{i}$ are the sizes of the parts $A_{i}$. So I want to prove that if $n=kq+r$, $0 \leq r < n$, $q = \lfloor \frac{n}{k} \rfloor$, $a_{1}= \space ... \space =a_{r}=q+1$, $a_{r+1}= \space ... \space =a_{k} = q$, and $b_{i}$ any other sequence of $k$ positive numbers such that $\sum_{i=1}^{k} b_{i} = n$, that $$\sum_{i=1}^{k} a_{i}(n-a_{i}) \geq \sum_{i=1}^{k} b_{i}(n-b_{i}).$$ Is there an elementary-inequality way of proving this? I've tried Lagrange multipliers, but it seems like overkill, and it'd require further discussion since $a_{i}$ can only be positive integers, not real numbers.

  • $\begingroup$ See Jensen’s Inequality. $\endgroup$ – Bob Krueger Nov 28 '17 at 18:01
  • $\begingroup$ @BobKrueger Jensen's inequality, and convexity in general, certainly underlie what's going on, but naively applying it still doesn't deal with the case where $\frac nk$ is not an integer. (It merely gives us an easy way to prove an upper bound of $n(n - \frac nk)$ on the number of edges, but this is not quite tight when $k$ does not divide $n$.) $\endgroup$ – Misha Lavrov Nov 28 '17 at 18:48

The only real way avoid "further discussion" to deal with the issue of integers is what they call a smoothing argument.

First, if we have $b_i - b_j\ge 2$ for any $i,j$, then replacing them by $b_i' = b_i - 1$ and $b_j' = b_j + 1$ while leaving all terms the same will increase the sum: $$\sum_{i=1}^k b_i (n-b_i) < \sum_{i=1}^k b_i' (n-b_i').$$ This is easy to check, since only two terms of the sum change, and the total change is by $2(b_i - b_j - 1) > 0$.

Second, if some of the parts do not have size $\lfloor \frac nk \rfloor$ or $\lceil \frac nk \rceil$, then the largest part and the smallest part must differ in size by at least $2$:

  • The average size is $\frac nk$, so the largest part must have size at least $\lceil \frac nk \rceil$ and the smallest part must have size at most $\lfloor \frac nk \rfloor$.
  • If $\frac nk$ is not an integer, then this already guarantees a difference of $2$ unless the largest part has size exactly $\lceil \frac nk \rceil$ and the smallest part has size exactly $\lfloor \frac nk \rfloor$.
  • If $\frac nk$ is an integer, then any part of size less than $\frac nk$ forces a part of size greater than $\frac nk$, and vice versa.

In such a case, the inequality above shows that such a $k$-partite graph cannot have the maximum number of edges. This leaves the Turán graph as the only possibility.

  • $\begingroup$ Hm, this discussion occured to me, but I didn't think it would be this simple. Thank you! $\endgroup$ – Matija Sreckovic Nov 28 '17 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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