Chapter 13: Combinatorial Designs

Can every pair meet exactly once in a balanced schedule?

Imagine organizing a series of round-table discussions for seven team members ($v=7$). To encourage maximum collaboration without bias, every pair of participants must sit together in exactly one meeting ($\lambda=1$). Furthermore, to keep discussions small and focused, each meeting room can only hold three participants ($k=3$). Can we construct such a schedule?

What, Why, and Fundamental Concepts:

• What is a Combinatorial Design? A combinatorial design is an arrangement of a finite set of elements (called points or participants) into subsets (called blocks or meetings) such that specific balance conditions are satisfied across all combinations of elements.
• Why do we study them? Unbalanced schedules create bottlenecks: some participants work together repeatedly while others never interact. Balanced designs eliminate structural bias, ensuring fair resource distribution, equal pairwise interaction, and statistical orthogonality.
• Applications: Tournament scheduling, agricultural crop field-testing (split-plot designs), A/B testing in software development, statistical sampling, and hardware defect testing.

Regard participants as points and meetings as blocks, each a three-element subset of the point set. There are $\binom72=21$ total pairs among seven participants, and each meeting contains $\binom32=3$ pairs. Therefore, any successful schedule must have exactly $21 / 3 = 7$ meetings.

That calculation is necessary, but seven arbitrary triples can repeat some pairs and omit others. We need a construction and a verification of every incidence. We also distinguish a list of meetings from a timetable of simultaneous rounds: blocks may overlap, and the basic design conditions do not prohibit that overlap.

The only number-theory background needed for the first constructions is divisibility and modular arithmetic, reviewed in section 13.1. Later optional sections connect the same small design to finite geometry, orthogonality, and error correction.

13.1 Modular arithmetic foundations

For an integer $m\ge2$, write $a\equiv b\pmod m$ when $m$ divides $a-b$. We represent the residue classes by $\mathbb Z_m=\{0,1,\ldots,m-1\}$, with addition and multiplication followed by reduction modulo $m$. Thus $5+4\equiv2\pmod7$ and $3\cdot5\equiv1\pmod7$.

Translation Invariance: Adding a fixed residue $t$ permutes $\mathbb Z_m$: its inverse operation is subtracting $t$. For a subset $D$, write

$$ D+t=\{d+t\pmod m:d\in D\}. $$

Translation preserves differences, since $(d+t)-(e+t)\equiv d-e\pmod m$. This invariant will let us verify a whole family of blocks by checking one starting block.

Multiplication needs more care. A residue $a$ has a multiplicative inverse if some $u$ satisfies $au\equiv1\pmod m$. Such an inverse exists exactly when $\gcd(a,m)=1$, where $\gcd$ is the greatest common divisor. One direction follows because a common divisor must divide $au-1$ as well as $au$. For the other, Bézout's identity supplies integers $u,w$ with $au+mw=1$, making $u$ an inverse modulo $m$.

For a prime $p$, every nonzero residue has an inverse; these residues together with zero form the field $\mathbb F_p$. Multiplication by a nonzero residue is therefore a permutation. For instance, solving $3x\equiv2\pmod7$ gives $x\equiv5\cdot2\equiv3\pmod7$.

Cancellation fails for a noninvertible multiplier: modulo six, $2\cdot1\equiv2\cdot4$, although $1\not\equiv4$. Later Latin-square arguments will explicitly require invertible coefficients rather than silently cancelling them.

Exercise. Find the inverse of $2$ modulo seven and translate $\{0,1,3\}$ by six. Hint: look for a product congruent to one, then reduce each translated entry separately. Answer: the inverse is $4$, and the translated block is $\{6,0,2\}$.

13.2 Balanced incomplete block designs

A balanced incomplete block design, or BIBD, has a finite point set $X$ of size $v$ and a collection of $b$ blocks, each of size $k$, with every pair of distinct points lying together in exactly $\lambda$ blocks. Here $2\le k\lt v$ and $\lambda\ge1$. Repeated blocks are permitted if counted with multiplicity; all the constructions initially displayed here have distinct blocks, making them simple designs. “Incomplete” means each block contains fewer than all the points.

The design is also written $2$-$(v,k,\lambda)$. Every point lies in the same number $r$ of blocks (called the replication count). To prove this, fix a point $x$. Count pairs consisting of another point $y$ and a block containing both $x,y$. There are $\lambda(v-1)$ choices counted by $y$, while each block through $x$ contributes $k-1$. Hence

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

Counting point–block incidences in two ways (summing point degrees vs. summing block sizes) also gives

$$ vr=bk. $$

Thus

$$ r=\frac{\lambda(v-1)}{k-1},\qquad b=\frac{\lambda v(v-1)}{k(k-1)}. $$

Both must be integers. These equations constrain candidate parameters; they do not by themselves construct blocks or establish existence.

For the seven-point schedule, $v=7$, $k=3$, and the desired $\lambda=1$ require $r=3$, $b=7$. The displayed blocks have these replication counts, and section 13.5 supplies a uniform proof of pair balance.

Exercise. Could there be a $2$-$(8,3,1)$ design? Hint: calculate $r$. Answer: no, because $r=7/2$ cannot count blocks through a point.

13.3 Steiner triple systems

A Steiner triple system of order $v$, abbreviated $\operatorname{STS}(v)$, is a $2$-$(v,3,1)$ design: every pair occurs in exactly one triple. Such blocks must be distinct, since repeating a triple would repeat all three of its pairs. The single triple on three points is a trivial system; for larger orders, the blocks are incomplete in the sense of section 13.2.

The parameter equations specialize to

$$ r=\frac{v-1}{2},\qquad b=\frac{v(v-1)}6. $$

For $v\ge3$, integrality forces $v$ to be odd and $v(v-1)$ to be divisible by three. Combining these restrictions gives

$$ v\equiv1\text{ or }3\pmod6. $$

Kirkman's existence theorem says these conditions are also sufficient for $v\ge3$. We prove the arithmetic necessity here and construct order seven explicitly; the general sufficiency construction is not proved in this chapter. The theorem and the cyclic and binary descriptions of the order-seven system appear in Peter Cameron's Steiner triple system reference. webspace.maths.qmul.ac.uk

The seven triples from the opening form the Fano plane, the smallest finite projective plane. In the diagram below, the six straight lines and the central circle represent its seven blocks. Only the seven labeled dots are points of the design; an unmarked crossing creates no additional point.

For example, point $3$ lies in $B_0,B_2,B_3$, meeting partners $0,1,2,5,4,6$ exactly once. Every participant attends three meetings. Since seven is not divisible by three, these triples cannot be partitioned into simultaneous rounds in which everyone attends exactly one meeting. That extra property is called resolvability and is separate from pair balance.

Exercise. Are orders $9$ and $11$ arithmetically admissible? Hint: reduce them modulo six. Answer: $9\equiv3$ is admissible, requiring $r=4,b=12$; $11\equiv5$ is impossible because $b=110/6$ is not integral.

13.4 Latin squares and MOLS

A Latin square of order $n$ is an $n\times n$ array on $n$ symbols, with each symbol appearing exactly once in each row and each column. Two Latin squares are orthogonal when their superimposed entries give each ordered symbol pair exactly once among the $n^2$ cells. A family is mutually orthogonal, or MOLS, when every two distinct members are orthogonal.

What, Why, and Applications:

• What: Latin squares eliminate two-way experimental bias (rows and columns), while MOLS allow testing multiple independent factors simultaneously in a balanced $n \times n$ layout.
• Why: Enables testing $k$ variables with $n^2$ experimental runs instead of $n^k$ brute-force trials.
• Applications: Agricultural field trials (controlling for soil gradient and sunlight), Sudoku puzzles, error-correcting code construction, and cryptographic block cipher design.

For a prime $p$, label rows, columns, and symbols by $\mathbb F_p$. For each nonzero $a$, define

$$ L_a(r,c)=ar+c\pmod p. $$

Fixing $r$ makes the row a translation of all column labels. Fixing $c$ makes the column a translated nonzero multiple of the row labels. Both are permutations, so $L_a$ is Latin.

For $a\ne b$, a requested ordered pair $(u,w)$ occurs at a cell satisfying

$$ ar+c=u,\qquad br+c=w. $$

Subtract to obtain $(a-b)r=u-w$. The nonzero coefficient is invertible, giving a unique $r$, and then a unique $c$. Hence the $p-1$ squares $L_a$ form a MOLS family.

For $p=3$, the two squares are

$$ L_1=\begin{pmatrix}0&1&2\\1&2&0\\2&0&1\end{pmatrix}, \qquad L_2=\begin{pmatrix}0&1&2\\2&0&1\\1&2&0\end{pmatrix}. $$

Their ordered pairs, read row by row, are $(0,0),(1,1),(2,2)$; $(1,2),(2,0),(0,1)$; and $(2,1),(0,2),(1,0)$. These are all nine pairs exactly once.

The prime hypothesis matters for this residue-ring construction. Modulo four, $L_1(r,c)=r+c$ and $L_3(r,c)=3r+c$ are both Latin because $1,3$ are invertible. They are not orthogonal: cells $(0,0)$ and $(2,2)$ both give the ordered pair $(0,0)$. Their slope difference is not invertible.

Latin squares can arrange treatments so that every treatment appears once at each row and column level. Orthogonality balances pairs from two symbol assignments; it does not assert that arbitrary higher combinations are balanced.

Exercise. Over $\mathbb F_5$, where do $L_2,L_4$ give $(1,3)$? Hint: solve $(2-4)r=1-3$ first. Answer: $r=1,c=4$; the values are $2+4\equiv1$ and $4+4\equiv3$.

13.5 Difference sets and finite projective planes

Optional extension. The foundation does not require this section. A cyclic group here simply means the residues with addition modulo $v$; translating all labels is a symmetry. The course roadmap lists the fuller treatments in sections 14.1, 42.1, and 42.2 on group actions, finite fields, and geometry.

A cyclic $(v,k,\lambda)$ difference set is a $k$-element subset $D\subseteq\mathbb Z_v$ such that every nonzero residue occurs exactly $\lambda$ times among the ordered differences $d-e$ with $d,e\in D$, $d\ne e$. Counting those differences gives

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

Use all $v$ translates $D+t$ as indexed blocks. A point $x$ appears in exactly $k$ blocks, one for each equation $t=x-d$ with $d\in D$. For distinct $x,y$, a block containing both corresponds to a representation $x-y=d-e$, with its translation uniquely determined by $t=x-d=y-e$. Thus the translates form a $2$-$(v,k,\lambda)$ design, with $b=v$ and $r=k$.

A projective plane of order $q\ge2$ has a unique line through any two distinct points, a unique intersection point of any two distinct lines, and four points with no three on a line; each line has $q+1$ points. A point outside a line joins its $q+1$ points by distinct lines, accounting for all lines through that point. Counting along those lines gives the parameters

$$ v=b=q^2+q+1,\qquad k=r=q+1,\qquad\lambda=1. $$

Our seven-point design realizes $q=2$. To check the line-intersection axiom, distinct triples meet in at most one point because pairs are unique. A fixed triple has three points, each on two other triples, accounting for all six other triples without repetition. Hence each other triple meets it exactly once. The four points $\{0,1,2,5\}$ contain no listed triple, supplying the remaining nondegeneracy axiom. The curved block in the drawing is a combinatorial line.

Exercise. Is $\{0,1,2\}$ a $(7,3,1)$ difference set? Hint: count the difference one. Answer: no; both $1-0$ and $2-1$ give one. Its translates put the pair $\{0,1\}$ in two blocks, so the same parameter equation does not ensure a design.

13.6 Orthogonal arrays

Optional extension. An orthogonal array $\operatorname{OA}(N,m,s,t)$ has $N$ rows, $m$ columns, and entries from an alphabet of $s$ symbols. For every choice of $t$ columns, each ordered $t$-tuple occurs exactly $\ell$ times, where the index satisfies $N=\ell s^t$. Rows are often experimental runs and columns are factors. Repeated rows are allowed in the general definition.

The two order-three Latin squares produce the following array. Each row is $(r,c,L_1(r,c),L_2(r,c))$.

This is $\operatorname{OA}(9,4,3,2)$ with index one. The columns $r,c$ contain every cell once. A row or column coordinate paired with either Latin symbol gives every ordered pair once by the Latin property. The two symbol columns do so by orthogonality. These exhaust the six column pairs.

More generally, $h$ MOLS of order $n$ give $\operatorname{OA}(n^2,h+2,n,2)$ by adjoining the row and column coordinates. Conversely, in an index-one strength-two array, designate two columns as row and column coordinates. Their pairs identify all $n^2$ cells uniquely; each remaining column becomes a Latin square, and pairs of remaining columns establish mutual orthogonality.

The array balances pairs of factor levels using nine runs rather than all $3^4=81$ full factorial combinations. It does not reproduce all triple or quadruple combinations, so pairwise balance must not be used as a claim about every interaction.

Exercise. Delete the $L_2$ column. What array remains, and does it have strength three? Hint: three ternary columns have $27$ possible triples. Answer: $\operatorname{OA}(9,3,3,2)$; it cannot have strength three because nine rows cannot contain each of those $27$ triples equally often with positive integer index.

13.7 Hadamard matrices and design constructions

Optional extension. A Hadamard matrix of order $n$ is an $n\times n$ matrix with entries $+1,-1$ satisfying $HH^{\mathsf T}=nI_n$, where $H^{\mathsf T}$ is its transpose and $I_n$ is the identity matrix. Rows have squared length $n$ and distinct rows have dot product zero.

For example,

$$ H_4=\begin{pmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{pmatrix} $$

has orthogonal rows. For two distinct rows, half their entries agree and half disagree, making their dot product zero.

Changing a row or column sign preserves orthogonality. We may therefore normalize the first row and first column to all ones. If $n>2$, the second row has equally many plus and minus signs. The third row must have equally many plus signs in each half distinguished by the second row, since it is orthogonal to both preceding rows. Thus $n$ must be divisible by four. This is a necessary condition, not a construction for every allowed order.

A concrete construction doubles an existing Hadamard matrix:

$$ H_{2n}=\begin{pmatrix}H_n&H_n\\H_n&-H_n\end{pmatrix}. $$

Block multiplication gives $H_{2n}H_{2n}^{\mathsf T}=2nI_{2n}$ because the off-diagonal blocks cancel. Starting with $H_1=(1)$ yields all orders that are powers of two.

Now take a normalized matrix of order $4u$, with $u\ge2$, and remove its first row and column. Use the remaining $4u-1$ columns as points; the plus positions in each remaining row form a block. Each row has $2u-1$ plus positions. Orthogonality of the original columns gives the same number $2u-1$ of blocks through each point, and any two points share $u-1$ blocks. To see the latter count, their core columns have dot product $-1$; if $a$ positions are plus in both, that dot product is $4a-4u+3$, forcing $a=u-1$.

We obtain a $2$-$(4u-1,2u-1,u-1)$ design. In particular, the order-eight matrix gives a $2$-$(7,3,1)$ design. The normalization and design constructions are described in Cameron's Hadamard-matrix notes. webspace.maths.qmul.ac.uk

Exercise. What design parameters come from a normalized order-sixteen matrix? Hint: set $u=4$. Answer: $v=b=15$, $k=r=7$, and $\lambda=3$; check $7\cdot6=3\cdot14$.

13.8 t-designs and Fisher-type inequalities

Optional extension. A $t$-$(v,k,\lambda)$ design is a collection of $k$-element blocks on $v$ points such that every $t$-element subset lies in exactly $\lambda$ blocks. Assume $1\le t\le k\le v$ and $\lambda>0$. For $0\le s\le t$, fix an $s$-element subset $S$. Count pairs $(T,B)$ with $S\subseteq T\subseteq B$ and $|T|=t$. Counting first by $T$, then by blocks containing $S$, gives

$$ \lambda_s\binom{k-s}{t-s} =\lambda\binom{v-s}{t-s}, \qquad \lambda_s=\lambda\frac{\binom{v-s}{t-s}}{\binom{k-s}{t-s}}. $$

Here $\lambda_s$ is the number of blocks through $S$, independent of which $S$ was chosen. In particular, $b=\lambda_0$ and $r=\lambda_1$. These quantities must be integers.

For example, all four-element subsets of a six-point set form a $3$-$(6,4,3)$ design: each triple extends to a block in three ways. The formulas give $b=15$, $r=10$, and $\lambda_2=6$.

Fisher's inequality. Every $2$-$(v,k,\lambda)$ design with $2\le k\lt v$ and $\lambda>0$ satisfies $b\ge v$. Form its $v\times b$ incidence matrix $A$, with entry one when a point belongs to a block. Dot products of its rows give

$$ AA^{\mathsf T}=(r-\lambda)I_v+\lambda J_v, $$

where $J_v$ is the all-ones matrix. The parameter equation and $v>k$ imply $r>\lambda$. For any nonzero real column vector $z$,

$$ z^{\mathsf T}AA^{\mathsf T}z =(r-\lambda)\sum_i z_i^2+\lambda\left(\sum_i z_i\right)^2>0. $$

Thus the rows of $A$ are linearly independent: a nonzero row dependence would make this expression zero. There cannot be more independent rows than columns, so $v\le b$. This is the proof mechanism: pair balance turns a counting problem into a positive definite matrix.

The Fano plane attains equality, $b=v=7$. Conversely, hypothetical parameters $v=16,k=6,\lambda=1$ give integer values $r=3,b=8$ satisfying both parameter equations, but Fisher's inequality rules out the design. Integrality alone is not enough.

A higher-strength extension is the Ray–Chaudhuri–Wilson bound: if a $2s$-$(v,k,\lambda)$ design has $2s\le k$ and $v\ge k+s$, then

$$ b\ge\binom vs. $$

Its proof replaces point rows by rows indexed by $s$-subsets and establishes their independence; that additional rank argument is not proved here. See Ray-Chaudhuri and Wilson's original paper, “On t-designs”. ir.library.osaka-u.ac.jp The complete $4$-$(6,4,1)$ design has $15=\binom62$ blocks, meeting this bound with $s=2$.

Exercise. For the complete $3$-$(6,4,3)$ design, count blocks through a fixed pair directly. Hint: choose two additional points from the remaining four. Answer: $\binom42=6$, agreeing with $\lambda_2$.

13.9 Connections to error-correcting codes

Optional extension. A binary word is a vector of zeros and ones. Its Hamming weight counts its ones, and the Hamming distance between two words counts coordinates where they differ. A code is a set of words; if its minimum distance is at least $2e+1$, it can correct up to $e$ changed bits by nearest-codeword decoding. Otherwise one received word could be within $e$ changes of two codewords, whose mutual distance would be at most $2e$. Sections 41.1 and 41.2 on the course roadmap give the fuller distance and linear-code theory.

First, replace each Fano block by its seven-coordinate incidence vector. Each word has weight three. Distinct blocks meet in one point, so their distance is $3+3-2=4$. These seven words form a constant-weight code correcting one bit error.

A different construction gives the binary $[7,4,3]$ Hamming code. Label our seven points by these nonzero vectors over $\mathbb F_2$, where addition is coordinatewise modulo two:

Put these vectors into the columns of the parity-check matrix

$$ H=\begin{pmatrix} 1&0&0&1&0&1&1\\ 0&1&0&1&1&1&0\\ 0&0&1&0&1&1&1 \end{pmatrix}, \qquad \mathcal C=\{c\in\mathbb F_2^7:Hc=0\}. $$

Words here are column vectors, with coordinates ordered $0,\ldots,6$. The first three columns are the identity, so four freely chosen coordinates determine the other three. Hence $\mathcal C$ has $2^4=16$ words. No weight-one word lies in the kernel because no column is zero. No weight-two word does because columns are distinct. A weight-three word exists—for example, the incidence vector of $B_0$—so the minimum nonzero weight is three. Since differences of codewords are codewords, the minimum distance is also three.

Every block triple has $h_i+h_j+h_k=0$. Conversely, any two distinct nonzero vectors have a third distinct nonzero vector as their sum, determining a unique triple. There are $21$ point pairs and three pairs per triple, so the seven Fano blocks are exactly the weight-three supports in $\mathcal C$.

For a received word $y=c+e_j$ with one error in coordinate $j$, the syndrome is $Hy=h_j$. Its nonzero value identifies that coordinate uniquely; flipping the bit recovers $c$. For example, $c=1101000$ is the word supported on $B_0$. An error at coordinate $4$ gives $y=1101100$, whose syndrome is $(0,1,1)=h_4$. Correcting that coordinate returns $1101000$. The single-error assumption is required; multiple errors need not be decoded correctly by this rule. This parity-check method is developed in Peter Shor's Hamming-code notes. math.mit.edu

Exercise. If the syndrome is $(1,0,1)$ and at most one bit was corrupted, which coordinate should be flipped? Hint: use the vector table. Answer: coordinate $6$.

Construct a small design and verify its parameter equations

The same seven-point object has appeared as a balanced meeting schedule, a modular translation family, a projective plane, and the supports of the Hamming code's weight-three words. Its usefulness comes from verified incidence rules: arithmetic generates candidates, while pair counts establish the design.

For an experimental application, use points as treatments and blocks as small testing batches. A BIBD places each treatment in equally many batches and compares each treatment pair together equally often. Those combinatorial properties support balanced comparisons; statistical conclusions still depend on the experiment's measurement model. In coding, adding redundancy uses a different balance: distinct nonzero parity-check columns distinguish single-bit error locations.