Computing the Turán Number t_r(n)

From Balanced Parts to an Edge Count

In an extremal graph problem, the construction and the count are separate tasks. For Turán numbers, the relevant construction is a complete multipartite graph: vertices in different parts are adjacent, while vertices in the same part are not. The balanced construction distributes the vertices as evenly as possible. Once the part sizes are known, its edge count can be computed by counting pairs in different parts.

Throughout, \(n\) and \(r\) are positive integers, and graphs are finite and simple. A graph is complete \(r\)-partite if its vertex set is partitioned into \(r\) parts and two distinct vertices are adjacent exactly when they lie in different parts. Parts may be empty. This convention is useful when \(r>n\).

The division \(n=qr+s\) determines the sizes: assigning \(q\) vertices to each of the \(r\) parts uses \(qr\) vertices, and the remaining \(s\) vertices raise \(s\) of those parts to size \(q+1\). The order of the parts does not matter, so this specifies \(T_r(n)\) up to isomorphism.

The Turán number \(t_r(n)\) is the maximum number of edges in a graph on \(n\) vertices that contains no complete subgraph \(K_{r+1}\). The standard Turán theorem, proved later in the course, identifies this maximum with the number of edges in \(T_r(n)\). Here we derive that construction's edge count and use it to calculate the number; the theorem that no other \(K_{r+1}\)-free graph has more edges is not being proved here.

Deriving the Formula

Let the part sizes of \(T_r(n)\) be \(a_1,\ldots,a_r\), so that \(\sum_{i=1}^r a_i=n\). For every pair of distinct parts \(i,j\), there are \(a_i a_j\) edges between them: each choice of one vertex from each part gives one edge. No edge lies within a part. Therefore the total edge count is the sum over all pairs of parts.

For the second equality, expand \((\sum_i a_i)^2\). The square terms sum to \(\sum_i a_i^2\), and each product \(a_i a_j\) with \(i<j\) occurs twice. Subtracting the square terms and dividing by two gives the stated expression.

For the balanced sizes, \(s\) parts have size \(q+1\), and \(r-s\) parts have size \(q\). Substitution gives the main calculation rule.

The expression is always an integer: it counts edges, or equivalently is the sum \(\sum_{i<j}a_i a_j\) of integer pair counts. Another useful way to compute it is to start with all pairs of vertices and subtract the pairs lying within the same part:

These are two forms of the same count. The first counts edges between parts directly. The second counts all possible vertex pairs and removes the nonedges within parts. The binomial coefficient \(\binom{a}{2}\) is zero when \(a=0\) or \(a=1\), so the second formula also applies when some parts are empty.

Why the Parts Are Balanced

The edge-count formula also explains the role of balancing. Consider any complete \(r\)-partite graph with part sizes \(a_1,\ldots,a_r\). If two parts have sizes \(a\) and \(b\), where \(a\ge b+2\), move one vertex from the part of size \(a\) to the part of size \(b\). The new sizes are \(a-1\) and \(b+1\). The sum of the squares of these two sizes changes by

Since the edge count is one half of \(n^2\) minus the sum of all part-size squares, this move increases the edge count by \(a-b-1\), a positive integer. Repeating such moves must stop: the sum of the squares is a nonnegative integer and decreases at every move. When no move is available, no two part sizes differ by two or more, so the sizes differ by at most one. Thus among complete \(r\)-partite graphs on \(n\) vertices, a balanced one has the largest edge count. This argument compares multipartite graphs; the broader extremal assertion for all \(K_{r+1}\)-free graphs is the content of Turán's theorem.

Worked Calculations

Common Pitfall: A Tempting Floor Formula

A frequent error is to assume that \(t_r(n)=\left\lfloor (1-1/r)n^2/2\right\rfloor\) for every \(n\) and \(r\). That expression does not always account for the difference between the part sizes. For example, with \(n=15\) and \(r=10\), division gives \(15=10\cdot1+5\). The balanced sizes are five parts of size \(2\) and five of size \(1\). Their squared sizes sum to \(5\cdot2^2+5\cdot1^2=20+5=25\), so the correct edge count is \((15^2-25)/2=(225-25)/2=100\).

The tempting expression instead gives \((1-1/10)\cdot15^2/2=(9/10)\cdot225/2=2025/20=101.25\), whose floor is \(101\), not \(100\). The part-size formula is the reliable calculation: first find \(q\) and \(s\), then use the actual balanced sizes. A floor shortcut should not replace that calculation unless its validity has been established for the particular setting.

For a quick reasonableness check, the result must be a nonnegative integer and no larger than \(\binom{n}{2}\), the number of all possible edges. In the \(n=15,r=10\) calculation, \(100\) satisfies both checks: \(0\le100\), and \(\binom{15}{2}=15\cdot14/2=105\), so \(100\le105\). These checks do not prove the arithmetic, but they can expose an impossible answer.

Using the Formula Reliably

For a new pair \((n,r)\), keep the calculation organized in this order:

1. Use integer division to write \(n=qr+s\) with \(0\le s<r\).
2. Record the part sizes: \(s\) copies of \(q+1\), followed by \(r-s\) copies of \(q\).
3. Count cross-part pairs with \(\sum_{i<j}a_i a_j\), or subtract within-part pairs from \(\binom{n}{2}\).
4. Check the result using the other counting method and verify it lies between \(0\) and \(\binom{n}{2}\).

The quotient and remainder handle equal parts automatically: when \(s=0\), all \(r\) parts have size \(q\). They also handle \(r>n\): then \(q=0\), exactly \(n\) parts are singletons, and the other \(r-n\) parts are empty. In either case, the same formulas apply without a separate edge-count rule.