Combinatorial Designs

Combinatorial design theory asks a deceptively simple question: can you arrange a finite collection of objects into groups so that every subset of a prescribed size appears in exactly the same number of groups? The answer — and the conditions under which it exists — turns out to be one of the richest problems in all of discrete mathematics, with roots going back to recreational puzzles of the nineteenth century and applications reaching forward into modern error-correcting codes, statistical experiment design, and cryptography. Design theory sits at the crossroads of combinatorics, algebra, and finite geometry, bringing together elegant counting arguments and deep structural theorems.

Block Designs and Balanced Incomplete Designs

Imagine that a medical researcher wants to test $k$ different treatments on groups of patients, but each patient can only receive $r$ treatments. A natural desideratum is that every pair of treatments is tested together on exactly $\lambda$ patients — no pair is favored or neglected. The mathematical abstraction of this situation is a balanced incomplete block design, or BIBD.

A BIBD with parameters $(v, b, r, k, \lambda)$ consists of a set $V$ of $v$ points (or varieties) and a collection $\mathcal{B}$ of $b$ blocks, each block being a $k$-element subset of $V$, such that every point appears in exactly $r$ blocks and every pair of distinct points appears together in exactly $\lambda$ blocks. The word “incomplete” signals that $k < v$: no single block contains all the points. When such a design exists it is often written $2\text{-}(v, k, \lambda)$, adopting the more general language of $t$-designs discussed below.

Three fundamental counting identities must hold for any BIBD. By double-counting incidences between points and blocks, every point lies in exactly $r$ blocks, so

$bk = vr.$

By double-counting pairs $(p, B)$ where $p$ is a pair of points and $B$ is a block containing both, one obtains

$r(k-1) = \lambda(v-1).$

These two equations are necessary arithmetic conditions — they must be satisfied by the parameters of any BIBD before one even begins to look for an actual construction. Checking these conditions is the first filter applied to any proposed parameter set.

A third, deeper necessary condition is Fisher’s inequality, proved by R. A. Fisher in 1940: in any BIBD with $v > k$, the number of blocks satisfies

$b \geq v.$

Fisher’s proof uses linear algebra. Consider the $b \times v$ incidence matrix $M$ whose $(i,j)$ entry is $1$ if point $j$ lies in block $i$ and $0$ otherwise. Computing the product $M^T M$ shows it equals $(\lambda - r)I + \lambda J$, where $I$ is the identity and $J$ is the all-ones matrix. Since $r > \lambda$ (when $v > k$), this matrix is non-singular, forcing $\text{rank}(M) = v$, and hence $b \geq v$.

The simplest non-trivial BIBD is the Fano plane, the unique $2\text{-}(7, 3, 1)$ design. It has $v = 7$ points and $b = 7$ blocks (called lines), each line containing exactly 3 points, each point on exactly 3 lines, and every pair of points lying on exactly 1 line. The Fano plane is the projective plane over the two-element field $\mathbb{F}_2$ and serves as the prototypical example of a finite geometry. Its seven lines are $\{1,2,4\}$, $\{2,3,5\}$, $\{3,4,6\}$, $\{4,5,7\}$, $\{5,6,1\}$, $\{6,7,2\}$, $\{7,1,3\}$ — each pair of points appearing together in exactly one line, confirming the design condition.

More generally, a projective plane of order $n$ gives a $2\text{-}(n^2 + n + 1, n + 1, 1)$ design: there are $n^2 + n + 1$ points, $n^2 + n + 1$ lines, each line has $n + 1$ points, each point lies on $n + 1$ lines, and any two points determine a unique line. Such planes exist whenever $n$ is a prime power — one constructs them from the projective geometry $PG(2, q)$ over the field $\mathbb{F}_q$ with $q = p^m$ elements. Whether projective planes of non-prime-power order can exist is one of the deepest open questions in combinatorics; it is known that no plane of order $10$ exists (proved by a massive computer search in 1989), but the general case remains unsettled.

Latin Squares and Orthogonal Arrays

A Latin square of order $n$ is an $n \times n$ array filled with $n$ distinct symbols such that each symbol appears exactly once in every row and exactly once in every column. The name reflects an old tradition — Leonhard Euler used Latin letters for such squares in his 1782 paper on the “36 officers problem,” and the terminology has stuck ever since. A simple example for $n = 3$ is:

$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{pmatrix}$

Latin squares can be thought of as multiplication tables for algebraic systems that are not quite groups: they correspond precisely to the Cayley tables of quasigroups — algebraic structures with a binary operation where every equation $a \cdot x = b$ or $y \cdot a = b$ has a unique solution. Every group’s Cayley table is a Latin square, but the converse fails.

Two Latin squares of the same order $n$ are orthogonal if, when one is superimposed on the other, every ordered pair of symbols $(i, j)$ appears exactly once among the $n^2$ superimposed cells. Euler’s 36 officers problem asked whether two orthogonal $6 \times 6$ Latin squares — one encoding regiment, one encoding rank — could be arranged so that every regiment-rank pair appeared exactly once. Euler conjectured in 1782 that no such pair could exist for any $n \equiv 2 \pmod{4}$, and the case $n = 6$ was confirmed laboriously by hand by Tarry in 1901. Astonishingly, Euler’s conjecture was demolished for all other cases in 1960 when Bose, Shrikhande, and Parker proved that orthogonal Latin squares exist for every order $n \geq 3$ except $n = 2$ and $n = 6$. This result, announced in the New York Times as the work of “three Indian mathematicians,” shocked the combinatorics community.

A set of $k$ mutually orthogonal Latin squares of order $n$ is denoted $\text{MOLS}(n,k)$. When $n = p^m$ is a prime power, one can construct a full set of $n - 1$ mutually orthogonal Latin squares using finite field arithmetic, and this maximum is achieved by the affine plane $AG(2,n)$. The maximum number of MOLS of order $n$ is denoted $N(n)$; bounding $N(n)$ from below and determining it precisely for non-prime-power orders are central open problems.

An orthogonal array $OA(N, k, s, t)$ is an $N \times k$ array with entries from an $s$-symbol alphabet such that in every $N \times t$ subarray, every $t$-tuple of symbols appears exactly $\lambda = N/s^t$ times. Latin squares are exactly $OA(s^2, 3, s, 2)$ arrays (each row records a triple $(i, j, L[i,j])$ for a Latin square $L$), and orthogonal Latin squares correspond to $OA(s^2, 4, s, 2)$ arrays. Orthogonal arrays were introduced by C. R. Rao in 1947 in the context of factorial experiments: choosing which factor combinations to test in an experiment so that all interactions of order $\leq t$ can be estimated independently. This statistical motivation drove much of early design theory and continues to shape its applications.

Steiner Systems and Triple Systems

A Steiner system $S(t, k, v)$ is a $t\text{-}(v, k, 1)$ design: a collection of $k$-element blocks from a $v$-element point set such that every $t$-element subset appears in exactly one block. These are the most “efficient” possible designs — each $t$-set is covered precisely once, with no redundancy. The definition was given in this generality by Jakob Steiner in 1853, though specific cases had appeared earlier.

The most famous is the Steiner triple system $S(2, 3, v)$, where we partition the pairs of a $v$-element set into triples such that each pair lies in exactly one triple. A triple system of order $v$ exists if and only if $v \equiv 1$ or $3 \pmod{6}$. The necessity of this condition is an easy arithmetic argument: with $v$ points and each block containing 3, the number of blocks is $b = v(v-1)/6$, which must be an integer. Sufficiency was established by Reiss in 1859: for all valid $v$, an explicit construction can be given.

The 36-student puzzle posed by Thomas Kirkman in 1847 — Kirkman’s schoolgirl problem — asks a refined question: can 15 schoolgirls walking in rows of 3 be arranged so that every pair walks together exactly once, and the seven daily walks can be organized into seven groups (called parallel classes) each covering all 15 girls? This is asking for a resolvable Steiner triple system $S(2, 3, 15)$. Kirkman answered affirmatively, and the general theory of resolvable designs was born. A resolvable $S(2, 3, v)$ is called a Kirkman triple system; such a system exists for all $v \equiv 3 \pmod{6}$.

Moving to the next level, a Steiner quadruple system $S(3, 4, v)$ requires that every triple of points appears in exactly one block of size 4. The necessary and sufficient condition is $v \equiv 2$ or $4 \pmod{6}$, proved by Hanani in 1960. The general existence question for Steiner systems $S(t, k, v)$ for arbitrary $t$ was settled only recently: in 2014, Peter Keevash proved using probabilistic and algebraic methods that $S(t, k, v)$ exists for all sufficiently large $v$ satisfying the necessary divisibility conditions. This was a landmark result, resolving a problem that had been open for over 150 years.

Counting the number of non-isomorphic Steiner triple systems of a given order reveals an explosion of complexity: there is 1 system of order 7 (the Fano plane), 1 of order 9 (the affine plane $AG(2,3)$), 80 of order 13, and the number grows super-exponentially. This combinatorial richness makes Steiner systems fascinating objects of study quite apart from their structural theory.

Applications to Coding Theory and Statistics

The connection between combinatorial designs and error-correcting codes is one of the most productive relationships in discrete mathematics, linking two fields that developed largely independently before their deep structural similarities were recognized.

A linear code $C$ of length $n$ and dimension $k$ over a finite field $\mathbb{F}_q$ is a $k$-dimensional subspace of $\mathbb{F}_q^n$. Its minimum distance $d$ is the smallest Hamming distance between two distinct codewords, where the Hamming distance between two words is the number of positions in which they differ. A code with minimum distance $d$ can detect up to $d - 1$ errors and correct up to $\lfloor (d-1)/2 \rfloor$ errors. Such a code is called an $[n, k, d]_q$ code.

The connection to designs arises through the supports of codewords. The support of a codeword $c$ is the set of coordinate positions where $c$ is nonzero. When the set of supports of all minimum-weight codewords in a linear code forms a $t$-design, the code and the design illuminate each other’s structure. The most celebrated example is the binary Hamming code $\text{Ham}(r, 2)$ of length $n = 2^r - 1$ and minimum distance 3. Its parity-check matrix has as columns all nonzero vectors in $\mathbb{F}_2^r$, and the code corrects exactly one error per codeword. The supports of its weight-3 codewords form a Steiner triple system $S(2, 3, 2^r - 1)$: every pair of coordinate positions appears in exactly one minimum-weight codeword. The Hamming code $\text{Ham}(3, 2)$ has parameters $[7, 4, 3]$ and its weight-3 words give exactly the Fano plane.

A code achieves the Hamming bound (also called the sphere-packing bound) with equality when the Hamming balls of radius $t = \lfloor (d-1)/2 \rfloor$ centered at codewords partition $\mathbb{F}_q^n$ exactly, with no overlap and no gaps. Such codes are called perfect codes. The Hamming codes are perfect, and so is the binary Golay code $G_{23}$, a $[23, 12, 7]$ code over $\mathbb{F}_2$. The supports of the weight-7 codewords in the Golay code form a Steiner system $S(4, 7, 23)$, while the extended Golay code $G_{24}$ (length 24) is related to $S(5, 8, 24)$, the remarkable Witt design. A theorem of Tietäväinen (1973), building on work of Lloyd, van Lint, and others, establishes that the only perfect single-error-correcting codes over prime alphabets are the Hamming codes, and the only perfect multiple-error-correcting binary codes are the Golay codes — a complete classification result of great elegance.

In statistics, the applications of design theory trace back to Ronald A. Fisher’s systematic development of experimental design at Rothamsted Experimental Station in the 1920s and 1930s. Fisher realized that the structure of a BIBD allows an experimenter to estimate treatment effects and contrasts without bias, even when nuisance factors (like variation in soil quality across an agricultural field) cannot be fully controlled. The key property is that a BIBD is variance-balanced: every normalized treatment contrast is estimated with the same variance, regardless of which pair of treatments is being compared. This statistical uniformity is the design-theoretic counterpart of the combinatorial balance condition $\lambda = \text{const}$.

The theory of factorial designs and orthogonal arrays continues this statistical tradition. In a $2^k$ factorial experiment, every combination of $k$ binary factors is tested; an orthogonal array $OA(N, k, 2, t)$ of strength $t$ selects a subset of $N$ runs such that all interactions of order $\leq t$ remain estimable. When $N$ is much smaller than $2^k$, the array achieves resolution — the ability to separate main effects from interactions — at a fraction of the cost of a full factorial experiment. The Plackett-Burman designs, published in 1946, are arrays of strength 2 achieving near-minimum run sizes; they are widely used in industrial quality engineering and pharmaceutical process optimization today.

Beyond statistics and coding theory, combinatorial designs appear in tournament scheduling (round-robin tournaments correspond to resolvable designs), cryptography (perfect difference sets underlie certain key-sharing schemes), and optical communication (optical orthogonal codes are designs with prescribed auto- and cross-correlation properties). The breadth of these applications reflects a simple underlying truth: whenever one requires a structured, balanced allocation of finite resources — experiment slots, communication channels, codeword positions — the mathematics of combinatorial designs is the natural language for both formulating and solving the problem.

The theory remains active. Construction of new families of designs, determination of the spectrum of achievable parameters, automorphism group classification, and connections to algebraic geometry via the theory of difference sets and character sums continue to generate new results. Design theory exemplifies how a question that begins with a concrete combinatorial puzzle — can I arrange these objects so that every pair appears equally often? — opens onto a vast landscape connecting algebra, geometry, probability, and applications across science and engineering.