EP05

EP05: Turán's Theorem and Counterpoint

极值图论

▶ 6:27 Graph TheoryCombinatorics

前置知识

EP04 All-Interval Rows and ℤ₁₂

后续拓展

EP06 Graph Coloring and Voice Assignment

小红书 Watch on 小红书

Overview

How many simultaneous intervals can a polyphonic texture contain before forbidden structures inevitably appear? In 1941, the Hungarian mathematician Pál Turán gave a precise answer to the general question: given $n$ vertices and no complete subgraph $K_{r+1}$ , the maximum number of edges is achieved by a unique graph called the Turán graph $T(n,r)$ .

This episode applies Turán’s theorem to Western counterpoint. Model the twelve pitch classes as vertices and “permitted simultaneous intervals” as edges. Forbidden parallels (parallel fifths, parallel octaves) and unstable intervals translate directly into forbidden cliques. Turán’s bound then governs the maximum polyphonic density achievable under any given set of contrapuntal rules — and the historical evolution from medieval organum to Renaissance polyphony traces a path along a rising Turán bound.

A second thread uses the Orbit-Stabilizer theorem from group theory (introduced in EP04) to count how many essentially distinct chord types exist under transposition symmetry, explaining why the most harmonically symmetric chords (augmented triads, diminished seventh chords) have the fewest distinct forms.

中文: “Turán定理描述的不是声音，而是约束如何塑造结构。每一条禁令，都在雕刻和声的精确边界。”

Prerequisites

All-Interval Rows and $\mathbb{Z}_{12}$ (EP04) — cyclic group of pitch classes, group actions, orbit-stabilizer theorem
Basic graph theory: vertices, edges, complete graph $K_n$ , complete bipartite graph $K_{m,n}$

Definitions

Def 5.1 (Complete Graph and Complete Bipartite Graph)

The complete graph $K_n$ has $n$ vertices with every pair connected by an edge; it has $\binom{n}{2}$ edges.

The complete bipartite graph $K_{m,n}$ has two disjoint vertex sets of sizes $m$ and $n$ ; every vertex in one set is connected to every vertex in the other, giving $mn$ edges. No edges exist within either set.

Def 5.2 (Turán Graph)

The Turán graph $T(n,r)$ is the complete $r$ -partite graph on $n$ vertices whose $r$ parts are as nearly equal in size as possible. Concretely, write $n = qr + s$ with $0 \le s < r$ ; then $s$ parts have $q+1$ vertices and $r-s$ parts have $q$ vertices. All edges between different parts are present; no edges within any part.

$T(n,r)$ has

e(T(n,r)) = \frac{r-1}{2r}\bigl(n^2 - s^2\bigr) + \binom{s}{2}

edges. For the asymptotic statement it suffices to remember the leading term:

e(T(n,r)) = \left(1 - \frac{1}{r}\right)\frac{n^2}{2} + O(n).

Def 5.3 (Extremal Number)

For a graph

H

, the extremal number

\mathrm{ex}(n, H)

is the maximum number of edges in an

n

-vertex graph that contains no subgraph isomorphic to

H

Def 5.4 (Contrapuntal Interval Graph)

Given a set of allowed intervals $\mathcal{A} \subseteq \{0,1,\ldots,11\}$ , define the contrapuntal interval graph $G_\mathcal{A}$ with vertex set $\mathbb{Z}_{12}$ (the twelve pitch classes arranged around a clock face) and an edge $\{i,j\}$ whenever the interval $|i-j| \bmod 12$ or $12 - (|i-j| \bmod 12)$ belongs to $\mathcal{A}$ .

A clique of size $r$ in $G_\mathcal{A}$ is a set of $r$ pitch classes that are pairwise connected by allowed intervals — a maximally consonant $r$ -note chord under the rules encoded by $\mathcal{A}$ .

Main Theorems

Theorem 5.1 (Turán's Theorem)

Let $G$ be a graph on $n$ vertices with no complete subgraph $K_{r+1}$ (i.e., no clique of size $r+1$ ). Then

|E(G)| \le e(T(n,r)) = \left(1 - \frac{1}{r}\right)\frac{n^2}{2} + O(n).

Moreover, equality holds if and only if $G \cong T(n,r)$ . The Turán graph is the unique extremal graph.

Proof.

We give the elegant probabilistic / double-counting proof.

Step 1 (Zykov symmetrization). Call a graph $r$ -partite if its vertices can be partitioned into $r$ independent sets. Any graph with no $K_{r+1}$ is $r$ -partite (since a graph is $r$ -partite iff its clique number $\omega \le r$ ; this follows from the fact that $K_{r+1}$ requires $r+1$ mutually adjacent vertices). [Alternatively this follows from Ramsey theory, or by induction on $n$ .]

Step 2 (Counting within a partition). Let $G$ have parts $V_1, \ldots, V_r$ with $|V_i| = n_i$ and $\sum n_i = n$ . Since there are no edges within parts, the edge count is

|E(G)| \le \sum_{1 \le i < j \le r} n_i n_j = \frac{1}{2}\left[\left(\sum_i n_i\right)^2 - \sum_i n_i^2\right] = \frac{n^2 - \sum_i n_i^2}{2}.

Step 3 (Optimize over partitions). By the convexity of $x^2$ , $\sum_i n_i^2$ is minimized when all $n_i$ are as equal as possible, i.e., when $|n_i - n_j| \le 1$ for all $i,j$ . This exactly describes $T(n,r)$ .

Step 4 (Equality). Equality holds when: (a) $G$ is complete $r$ -partite (all inter-part edges present), and (b) parts are as equal as possible. These two conditions uniquely determine $T(n,r)$ up to isomorphism. $\square$

Theorem 5.2 (Mantel's Theorem)

The maximum number of edges in a triangle-free graph on

n

vertices is

\lfloor n^2/4 \rfloor

, achieved uniquely by

K_{\lfloor n/2 \rfloor,\, \lceil n/2 \rceil} = T(n,2)

Proof.

This is Turán’s theorem with $r = 2$ : no $K_3$ means the graph is bipartite ($2$-partite), and the unique maximum bipartite graph on $n$ vertices is the balanced complete bipartite graph $K_{\lfloor n/2\rfloor, \lceil n/2\rceil}$ , which has $\lfloor n^2/4 \rfloor$ edges.

Mantel’s original 1907 proof uses a neat counting argument: let $d_v$ be the degree of vertex $v$ . For any edge $\{u,v\}$ , since $G$ is triangle-free $u$ and $v$ share no common neighbor, so $d_u + d_v \le n$ . Summing over all edges gives $\sum_{\{u,v\}\in E} (d_u + d_v) \le n|E|$ . The left side equals $\sum_v d_v^2$ (each vertex $v$ contributes $d_v$ to the sum for each of its $d_v$ edges). By Cauchy-Schwarz, $\sum_v d_v^2 \ge \frac{(\sum_v d_v)^2}{n} = \frac{4|E|^2}{n}$ . Combining: $4|E|^2/n \le n|E|$ , so $|E| \le n^2/4$ . $\square$

Theorem 5.3 (Orbit-Stabilizer Theorem (applied to chords))

The group $\mathbb{Z}_{12}$ acts on the set of $k$ -element subsets of $\mathbb{Z}_{12}$ by transposition $T_m(S) = \{s + m \bmod 12 : s \in S\}$ . For any chord $S$ :

|\mathrm{Orb}(S)| \cdot |\mathrm{Stab}(S)| = 12

where $\mathrm{Stab}(S) = \{m \in \mathbb{Z}_{12} : T_m(S) = S\}$ is the stabilizer (the set of transpositions that map $S$ to itself).

Proof.

This is the standard Orbit-Stabilizer theorem from group theory. The map

\mathbb{Z}_{12}/\mathrm{Stab}(S) \to \mathrm{Orb}(S)

defined by

[m] \mapsto T_m(S)

is a well-defined bijection:

T_m(S) = T_{m'}(S)

iff

T_{m-m'}(S) = S

iff

m - m' \in \mathrm{Stab}(S)

iff

[m] = [m']

. Therefore

|\mathrm{Orb}(S)| = |\mathbb{Z}_{12}/\mathrm{Stab}(S)| = 12/|\mathrm{Stab}(S)|

, giving the formula.

\square

Prop 5.1 (Turán Bound for the Interval Graph)

For the contrapuntal interval graph $G_\mathcal{A}$ on 12 pitch classes with no allowed clique of size $r+1$ :

|E(G_\mathcal{A})| \le \left(1 - \frac{1}{r}\right) \cdot 36.

In particular, if triads ( $K_3$ ) are forbidden ( $r = 2$ ): $|E| \le 36$ . If four-note chords ( $K_4$ ) are forbidden ( $r = 3$ ): $|E| \le 48$ .

Visual: A clock-face of 12 pitch-class nodes; edges light up as $\mathcal{A}$ expands from $\{0,5,7\}$ (medieval) to $\{0,3,4,7,8,9\}$ (Renaissance), with a running edge count approaching the Turán bound.

Musical Connection

音乐联系

Counterpoint rules as forbidden cliques

Western counterpoint evolved in stages, each corresponding to an expansion of the allowed interval set $\mathcal{A}$ and a corresponding rise in the Turán bound.

Era	Allowed intervals $\mathcal{A}$	Forbidden clique size	Turán bound $\mathrm{ex}(12, K_{r+1})$
Medieval organum	$\{0, 5, 7\}$ (unison, 4th, 5th)	$K_3$	36 edges
Renaissance (Palestrina)	$\{0, 3, 4, 7, 8, 9\}$ (+ thirds, sixths)	$K_4$	48 edges
Common practice	all intervals except augmented/diminished 4ths/5ths	$K_5$	54 edges
Modern chromatic	near-complete	$K_{13}$ (trivial)	66 edges

The most important medieval prohibition is parallel fifths and octaves: two voices may not move in the same direction by a perfect fifth (or octave) simultaneously. In graph terms, this constrains which edges may co-occur dynamically (a temporal constraint), not merely which edges exist. The static Turán bound gives a necessary condition on polyphonic density; the dynamic parallel-motion rules give additional linear-algebraic constraints on voice-leading paths through the graph.

Chord symmetry and ambiguity

The Orbit-Stabilizer theorem explains why certain chords are harmonically “slippery”:

Major triad $\{0,4,7\}$ : $\mathrm{Stab} = \{0\}$ , $|\mathrm{Orb}| = 12$ . Twelve distinct major triads, each pointing unambiguously to one key.
Augmented triad $\{0,4,8\}$ : $\mathrm{Stab} = \{0,4,8\}$ , $|\mathrm{Orb}| = 4$ . Only four distinct augmented triads; Liszt and Wagner exploited this to pivot between three keys simultaneously.
Diminished seventh chord $\{0,3,6,9\}$ : $\mathrm{Stab} = \{0,3,6,9\}$ , $|\mathrm{Orb}| = 3$ . Only three distinct diminished seventh chords; the ultimate modulation tool of Romanticism.
Whole-tone scale $\{0,2,4,6,8,10\}$ : $|\mathrm{Stab}| = 6$ , $|\mathrm{Orb}| = 2$ . Debussy’s floating, directionless sonority comes from having only two whole-tone collections.

By Burnside’s lemma, the total number of essentially distinct three-note chord types under transposition is exactly 19, and four-note chord types is 43. This is the complete mathematical map of harmonic space.

Numerical Examples

Turán numbers for $n = 12$ vertices:

\mathrm{ex}(12, K_3) = \left(1 - \frac{1}{2}\right)\frac{144}{2} = 36 \quad \Leftrightarrow \quad K_{6,6}

\mathrm{ex}(12, K_4) = \left(1 - \frac{1}{3}\right)\frac{144}{2} = 48 \quad \Leftrightarrow \quad T(12,3) = K_{4,4,4}

\mathrm{ex}(12, K_5) = \left(1 - \frac{1}{4}\right)\frac{144}{2} = 54 \quad \Leftrightarrow \quad T(12,4) = K_{3,3,3,3}

The fact that $\mathrm{ex}(12, K_3) = 36$ is achieved by $K_{6,6}$ has an elegant musical coincidence: the whole-tone scale divides the twelve pitch classes into exactly two groups of six ( $\{0,2,4,6,8,10\}$ and $\{1,3,5,7,9,11\}$ ), which is the vertex bipartition of $K_{6,6}$ .

Limits and Open Questions

Dynamic vs. static constraints. Turán’s theorem addresses static graph density. The counterpoint rules for parallel motion are inherently dynamic: they constrain sequences of simultaneously sounding intervals. A full mathematical treatment requires modeling voice-leading as paths in a product graph, connecting to the work of Tymoczko on voice-leading geometry.
Non-graph-theoretic interval constraints. Some contrapuntal rules involve absolute pitch height (e.g., avoid crossing voices), orchestration timbre, and metric accent — none of which are captured by the pitch-class graph model.
Extremal combinatorics of other forbidden patterns. Zarankiewicz’s problem asks for the maximum edges in a bipartite graph with no complete bipartite subgraph $K_{s,t}$ . In a musical reading, this would model textures where no group of $s$ upper-voice notes may all be consonant with every one of $t$ bass notes.
Burnside count for rhythm. Analogous to counting chord types, one can count essentially distinct rhythmic patterns of length $n$ under rotation and reflection — a direct application of Burnside’s lemma to dihedral groups, relevant to tala (Indian rhythmic cycles) and African polyrhythm.

Academic References

Turán, P. (1941). On an extremal problem in graph theory. Matematikai és Fizikai Lapok, 48, 436–452. (Hungarian; the theorem that started extremal graph theory.)
Bollobás, B. (1978). Extremal Graph Theory. Academic Press. Ch. 2–3 (Turán-type results).
Aigner, M., & Ziegler, G. M. (2018). Proofs from THE BOOK (6th ed.). Springer. “Turán’s Graph Theorem” chapter (Mantel’s proof).
Tymoczko, D. (2011). A Geometry of Music. Oxford University Press. Ch. 2 (Voice-leading and chord geometry).
Forte, A. (1973). The Structure of Atonal Music. Yale University Press. (Pitch-class set theory and the 219 chord types.)
Guerino Mazzola (2002). The Topos of Music. Birkhäuser. (Categorical and topological approach to harmony.)
Knopoff, L., & Hutchinson, W. (1983). Entropy as a measure of style. Journal of Music Theory, 27(1), 75–97.