In this article, we discuss a proof of the celebrated Turán’s theorem that uses the Probabilistic Method and the famous Cauchy-Schwarz inequality. Turán’s theorem is named after Pál Turán, one of the many brilliant combinatorialists and number theorists that Hungary has produced.

The setting of the theorem is quite simple. Suppose that you have N vertices, and the task is to start adding edges in between them in order to construct a simple graph with no parallel edges that has as many edges as possible. Clearly, if there are no constraints, then we can always make all possible connections and end up with the complete graph (clique), which has N(N-1)/2 edges.

Let’s make things a bit more interesting. Our goal again is to start adding edges, starting from the empty graph on N vertices, and we would like to add as many edges as possible, with the constraint that the resulting graph we construct does not contain a clique of size k+1, for some given integer parameter k. In other words, we must never produce a subset of vertices of size k+1 for which all vertices of the subset are connected with each other. The question then is the following:

Given N vertices and a natural number k, what is the largest number of edges between vertices that we can add without creating a clique of size k+1?

Such questions fall into the field of study known as Extremal Combinatorics. Turán’s theorem answers exactly this question.

[Turán’s theorem (1941)] Suppose G = (V, E) is a simple graph on Nvertices that does not contain a clique of size k+1, for some natural number k > 0. Then,

As a clarification, a simple graph is a graph with no parallel edges and not self-loops.

There are many proofs of the above theorem; an obvious way to go is to try induction on the number of vertices N. But, today we will discuss an elegant proof that uses the Probabilistic Method and the Cauchy-Schwartz inequality and is due to Alon and Spencer. For a quick introduction to the concept of the Probabilistic Method, you can check a previous article of mine here.

Before proving Turán’s theorem, we present a quick proof of the Cauchy-Schwarz inequality. If you are familiar with the inequality, feel free to skip this next subsection.

We note that the exposition from now on follows closely the relevant chapters of the book: “Proofs from THE BOOK” by Martin Aigner and Günter M. Ziegler (Springer).

A short detour: the Cauchy-Schwartz inequality for Euclidean spaces

One of the most famous inequalities in all of mathematics is the Cauchy-Schwarzinequality (also known as the Cauchy–Bunyakovsky–Schwarz inequality). It is a general inequality about inner product spaces, but since we will only need a special case of the inequality, we provide the proof of that special case.

[Cauchy-Schwarz inequality] Let a = (a₁, …, aₙ) and b = (b₁, …, bₙ) be two n-dimensional real vectors. Then,

Proof. We define the following function on the real variable x:

It is clear that f(x) ≥ 0 for every x. By expanding, we get

Since the function f is a quadratic polynomial on x, and is non-negative, then its discriminant must be non-positive. Thus, we have

By rearranging the term, we obtain the desired inequality. We are done!

A proof of Turán’s theorem

We are now ready to prove Turán’s theorem. Let G = (V,E) be the given graph. Let ω(G) be the size of the largest clique in G. By assumption, we have that ω(G) ≤ k. We will now compute a lower bound on ω(G) that will involve the degrees of the vertices of G. For that, we introduce the notation dᵥ for the degree of a vertex v of G.

More precisely, we do the following randomized procedure. We pick a random permutation π of all vertices. We now construct the following set C(π). We process the vertices according to the permutation π, and for each vertex v, we add it to the set C(π) if all of the vertices preceding it in the permutation are neighbors of v in G.

By construction, observe that the set C(π) is always a clique. We will now compute its expected size (since C(π) is a random variable). We write X = |C(π)| for its size, and we have X = Σᵥ Xᵥ, where Xᵥ is the indicator random variable that is equal to 1 if the vertex v of G is added to C(π), and 0 otherwise.

Let’s now fix a vertex v and study Xᵥ. The variable is set to 1 if all vertices that precede v according to π are neighbors of v. Equivalently, it is set to 1 if all vertices that are not neighbors of v come after v according to the order π. So, let’s look at vertex v and all of its N-1-dᵥ non-neighbors. It is not hard to see that v will be added to C(π) if and only if it is the first among all of these N-dᵥ vertices (here, we also count v itself). Focusing only on these vertices, it is easy to see that the restriction of π on these vertices is still a random permutation, and thus, the probability that v comes first (i.e., it is in the first position of this restricted permutation) is equal to 1/(N-dᵥ). We conclude that

Thus, by using linearity of expectation, we get that

Since we are done with the random experiment, we now introduce some notation to simplify the exposition from now on. We arbitrarily index the vertices of V as

We also denote the degree of vertex vᵢ as dᵢ. Using this new notation, and since the expected size of the random clique we computed is equal to

this means that there must exist a clique in G with at least that size (otherwise, the expected value would have been smaller). But we know that every clique of Ghas size at most k, and so we conclude that

We are now ready to finish our proof. We use the Cauchy-Schwarz inequality that we described above, where for every i we set

Applying Cauchy-Schwarz to the vectors a and b, we get that

where we used the fact that the sum of all degrees is equal to 2|E| (see here in case you are not familiar with this fact). Rearranging the terms above, we conclude that

Turán’s theorem has been proved!

Tightness of Turán’s theorem

It is not hard to see that the inequality in Turán’s theorem is sometimes tight, and thus cannot be further improved (an improvement here means to reduce the right-hand side of the inequality even more). A family of graphs that shows that the inequality is tight is the so-called family of Turán graphs. Here is their construction:

• Split the vertex set V into k parts (for simplicity, assume that |V| = N is divisible by k).
• Connect two vertices if and only if they belong to different parts.

By construction, there is no clique of size larger than k, since, by the pigeonhole principle, this would mean that at least two vertices of that clique belong to the same part; this cannot happen as there are no edges between vertices that belong to the same part of the partition.

Let’s count now the number of edges in such graphs. Instead of directly counting the number of edges, we will actually count the number of edges that are missing. Inside each part, there are no edges, while all edges between vertices in different parts are included in our graph. This implies that

References

• https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem
• https://en.wikipedia.org/wiki/Tur%C3%A1n_graph
• “Proofs from THE BOOK” by Martin Aigner and Günter M. Ziegler. Springer.