Combinatorial Design Theory studies how to arrange finite sets of objects so that prescribed patterns of overlap, balance, and symmetry occur. The subject sits at the intersection of combinatorics, algebra, and geometry, and it asks questions that are both structural and constructive: when do such designs exist, how can they be built, and what do they reveal about the underlying finite system? Throughout the course, the central objects include Latin squares, quasigroups, block designs, projective and affine planes, Steiner systems, difference sets, and the codes naturally associated with them.

The chapters develop the theory in a deliberately cumulative way. The course begins with Latin squares and orthogonality, then moves to quasigroups and loops as algebraic language for construction. From there it introduces incidence structures and block designs, using Fisher’s inequality and linear algebra to obtain foundational constraints. Projective and affine planes provide a geometric setting, while Steiner triple systems and small designs offer concrete families and examples. Later chapters focus on resolvable designs and scheduling, cyclic constructions via difference sets, and the links between designs and error-correcting codes. The course closes with existence theorems and modern perspectives, tying together the algebraic, geometric, and coding-theoretic threads that run through the subject.

# Introduction

This opening chapter sets the direction for the course. Combinatorial design theory studies finite arrangements whose small pieces satisfy exact incidence rules: each symbol appears once in each row and column, each pair of points lies in a prescribed number of blocks, or each line in a finite geometry has a fixed size. The course begins with Latin squares and then moves toward block designs, Steiner systems, finite geometries, and existence theorems, with the recurring question of how local regularity forces global structure.

The emphasis is on constructions, necessary counting conditions, and structural obstructions. Some designs arise from algebraic systems such as groups and finite fields; others are ruled out by parity, divisibility, or linear algebra. Applications to experiments, tournaments, error-correcting codes, and finite projective planes will appear as motivation, but the course treats them through the common language of incidence.

## What Counts as a Design?

A first difficulty is that the word "design" covers several related objects rather than a single definition. The course will use it as an organising idea: a finite set of points, symbols, positions, or treatments is arranged so that prescribed patterns occur with controlled multiplicity.

[explanation: Incidence As The Organising Principle] Most designs in this course can be read as incidence structures. There is a collection of objects of one type, such as points, and a collection of objects of another type, such as blocks, lines, rows, columns, or symbols. The mathematical content lies in the incidence relation between them.

For Latin squares, incidence records which symbol occurs in which row-column position. For block designs, incidence records which points lie in which blocks. For finite projective planes, incidence records which points lie on which lines. The surface notation changes, but the same questions recur: how many objects must exist, how many incidences are forced, and when can a partial pattern be completed? [/explanation]

This viewpoint lets us compare objects that first look unrelated. A Latin square controls ordered pairs of row and column coordinates, while a balanced incomplete block design controls unordered pairs of points inside blocks. Both impose a uniformity condition on small subconfigurations.

[example: Three Small Incidence Rules] A Latin square of order $3$ can be seen explicitly by taking symbols $\{0,1,2\}$ and using the three rows $(0,1,2)$, $(1,2,0)$, and $(2,0,1)$. Each row contains each symbol once, and the three columns are \begin{align*} (0,1,2), \qquad (1,2,0), \qquad (2,0,1), \end{align*} so each column also contains each symbol once. A block design with block size $3$ can ask for every pair of points to occur together in exactly one block. For example, on points $\{1,2,3,4,5,6,7\}$, take the seven triples \begin{align*} 123,\quad 145,\quad 167,\quad 246,\quad 257,\quad 347,\quad 356. \end{align*} The triples containing $1$ give the pairs $12,13,14,15,16,17$; the triples containing $2$ give $21,23,24,26,25,27$; continuing through the listed triples shows that each point occurs with each of the other six points exactly once. A finite projective plane of order $2$ has seven points and seven lines, each line containing three points, and the seven triples above may be read as its seven lines. There are \begin{align*} \binom{7}{2}=21 \end{align*} pairs of distinct points, while the seven lines contain \begin{align*} 7\binom{3}{2}=7\cdot 3=21 \end{align*} point-pairs in total. Since the displayed triples account for each point-pair once, every pair of points lies on exactly one line. These three examples use different surfaces: arrays, triples, and lines, but in each case the local incidence counts are fixed before the whole configuration is built. [/example]

The next question is how to extract information before constructing anything. Counting incidences in two ways is the first technique, and it will appear throughout the course.

[quotetheorem:5718]

[citeproof:5718]

The principle is elementary, but its hypotheses are exactly what make the conclusion sharp. Finiteness ensures that the incidence set has a well-defined cardinality, and exact uniformity ensures that every fibre over $X$ has the same size $a$ and every fibre over $Y$ has the same size $b$. If either uniformity condition is weakened to an average or an upper bound, the equality need not survive. For instance, take $X=\{x_1,x_2\}$, $Y=\{y_1,y_2\}$, and $I=\{(x_1,y_1),(x_1,y_2),(x_2,y_1)\}$. The $X$-fibres have sizes $2$ and $1$, while the $Y$-fibres have sizes $2$ and $1$, so there is no common pair of constants $a,b$ for which $a|X|=b|Y|$ records the incidence count.

[example: A First Divisibility Obstruction] Suppose a finite incidence structure has point set $X$ with $|X|=v$ and block set $\mathcal{B}$ with $|\mathcal{B}|=b$. Assume every block has size $k$ and every point lies in exactly $r$ blocks. Let \begin{align*} I=\{(x,B)\in X\times \mathcal{B}: x\in B\} \end{align*} be the point-block incidence relation. Counting $I$ by points gives \begin{align*} |I|=\sum_{x\in X} r=vr, \end{align*} because each of the $v$ points is incident with exactly $r$ blocks. Counting the same set $I$ by blocks gives \begin{align*} |I|=\sum_{B\in \mathcal{B}} |B|=\sum_{B\in \mathcal{B}} k=bk, \end{align*} because each of the $b$ blocks contains exactly $k$ points. Hence, by the *[Double Counting Principle For Incidences](/theorems/5718)*, \begin{align*} vr=bk. \end{align*} Therefore a proposed regular incidence structure must have \begin{align*} r=\frac{bk}{v}, \end{align*} so $v$ must divide $bk$. For the proposed parameters $v=5$, $k=3$, and $b=6$, this would require \begin{align*} r=\frac{bk}{v} =\frac{6\cdot 3}{5} =\frac{18}{5}. \end{align*} Since a point cannot lie in a non-integer number of blocks, no incidence structure with these exact regularities exists. If the five points were allowed to lie in different numbers of blocks, then six triples would still have total incidence count \begin{align*} 6\cdot 3=18, \end{align*} but the point-side count would be a sum of five possibly different fibre sizes rather than $5r$, so the divisibility obstruction comes specifically from requiring one common replication number $r$. [/example]

## Latin Squares as the First Model

How can a multiplication table be useful if the operation is not the main object? The answer is that its row-column-symbol pattern is already a design, and many later constructions begin by forgetting algebraic operations while retaining their incidence regularity.

[definition: Latin Square] A Latin square of order $n$ on a symbol set $S$ with $|S|=n$ is a map \begin{align*} L: \{1,\dots,n\} \times \{1,\dots,n\} \to S \end{align*} such that, for each fixed row index $i$, the map $j \mapsto L(i,j)$ is a bijection from $\{1,\dots,n\}$ to $S$, and, for each fixed column index $j$, the map $i \mapsto L(i,j)$ is a bijection from $\{1,\dots,n\}$ to $S$. [/definition]

The definition isolates the cancellation property of a multiplication table without requiring associativity, an identity, or inverses in a group-theoretic sense. This separation is important because Latin squares form a much larger class than group tables.