Sources and References

Primary textbook — C. Godsil, Geometry: Finite, Real, Imaginary (course notes, 2026). Available at https://www.math.uwaterloo.ca/~cgodsil/CO434-634/

Supplementary texts — P.J. Cameron & J.H. van Lint, Designs, Graphs, Codes and Their Links (Cambridge, 1991); D.R. Stinson, Combinatorial Designs: Constructions and Analysis (Springer, 2004); E.F. Assmus & J.D. Key, Designs and Their Codes (Cambridge, 1992)

Online resources — C. Godsil’s CO 434/634 course page, University of Waterloo (https://www.math.uwaterloo.ca/~cgodsil/CO434-634/); MIT OCW 18.315 Combinatorial Theory; lecture notes from Peter Cameron (QMUL)

Chapter 1: Incidence Structures and Block Designs

The subject of combinatorial designs begins with a deceptively simple idea: arrange a finite set of objects into subsets subject to precise regularity conditions. The resulting structures — block designs, Steiner systems, Hadamard matrices, and their kin — sit at a remarkable intersection of combinatorics, linear algebra, finite geometry, and group theory. Godsil’s Geometry: Finite, Real, Imaginary approaches these objects through the lens of linear algebraic methods, and these notes follow that perspective throughout.

1.1 Incidence Structures

Every incidence structure has a natural graph-theoretic encoding. The incidence graph (or Levi graph) of \((P, B, I)\) is the bipartite graph with vertex set \(P \cup B\), where \(p \in P\) is adjacent to \(\beta \in B\) if and only if \((p, \beta) \in I\). This graph encodes the full combinatorial data of the structure and connects design theory to spectral graph theory.

The incidence matrix is the workhorse of the algebraic theory. Key properties of a design — regularity, intersection numbers, Fisher-type inequalities — all emerge from rank arguments and products involving \(N\).

Projective and affine planes are the canonical examples of linear spaces. Their rich geometry provides the prototypical constructions for the general theory of block designs.

1.2 Block Designs

The central objects of this course are designs that impose a uniform regularity on how points and blocks interact. The following definition captures the precise notion of a 2-design, also called a balanced incomplete block design (BIBD).

The five parameters \((v, b, r, k, \lambda)\) are not independent. Counting incidences in two different ways yields the fundamental parameter relations.

These relations are necessary but not sufficient for the existence of a design with given parameters. A pair \((v, k, \lambda)\) satisfying these arithmetic conditions is called admissible; whether an admissible set of parameters actually yields a design is a far deeper question, and much of the subject is devoted to it.

1.3 The Fano Plane

The Fano plane is the unique design with parameters \((7, 3, 1)\). It embodies much of the spirit of the subject: a tiny structure with enormous symmetry — its automorphism group is \(\mathrm{PSL}(2, 7)\) of order 168 — and connections running to coding theory (the Hamming code), group theory (the simple group \(\mathrm{GL}(3,2)\)), and geometry (the projective plane over \(\mathbb{F}_2\)).

1.4 Difference Sets

The Fano plane was constructed by taking the translates of a single set in an abelian group. This is the idea of a difference set.

Difference sets are a major source of symmetric designs. The quadratic residues modulo a prime \(p \equiv 3 \pmod{4}\) form a \(\left(\frac{p-1}{2}\right)\)-element difference set in \(\mathbb{Z}_p\) with \(\lambda = \frac{p-3}{4}\), giving the Paley designs. For example, the quadratic residues mod 7 are \(\{1, 2, 4\}\), yielding the Fano plane (up to relabelling).

1.5 Steiner Systems

At the opposite extreme from highly symmetric difference-set designs are Steiner systems, where \(\lambda = 1\): every pair of points lies in exactly one block.

Steiner triple systems are among the most studied objects in combinatorics. The smallest is the Fano plane (\(v = 7\)); the next is \(S(2, 3, 9)\), the affine plane \(\mathrm{AG}(2, 3)\), consisting of the \(12\) lines of the \(3 \times 3\) grid.

1.6 t-Designs

The definition of a 2-design extends naturally.

The derived parameter counting generalises cleanly.

The existence of a \(t\)-design requires that \(\lambda_s\) be a positive integer for all \(0 \leq s \leq t\). These divisibility conditions are necessary but generally not sufficient. The great existence theorem of Wilson (discussed in Chapter 5) shows they are asymptotically sufficient.

Chapter 2: Symmetric Designs and Fisher’s Inequality

2.1 Symmetric Designs

Among all 2-designs, those with \(b = v\) — equivalently, \(r = k\) — occupy a special position. They are called symmetric designs and their theory is substantially richer than the general case, largely because their incidence matrices are square.

The incidence matrix of a symmetric design satisfies a fundamental matrix identity. Since \(N\) is \(v \times v\) in this case, we can compute \(NN^T\) directly.

2.2 Fisher’s Inequality

One of the most elegant results in combinatorics is Fisher’s inequality, which asserts that a non-trivial 2-design must have at least as many blocks as points.

Fisher’s inequality was first proved by R.A. Fisher in the context of statistical design of experiments (1940). The algebraic proof via the matrix \(NN^T\) is due to Majumdar and later clarified by Bose. The positive-definiteness argument is a model for many results in algebraic combinatorics: encode a counting condition as a matrix identity, then use spectral information.

2.3 Block Intersection in Symmetric Designs

When \(b = v\), the incidence matrix is square and invertible (by Fisher’s proof). This gives a strikingly clean description of how blocks intersect.

The self-duality of symmetric designs is a beautiful feature absent in the general case. The Fano plane is self-dual: its dual is again the Fano plane (up to isomorphism).

2.4 Projective Planes as Symmetric Designs

The standard construction uses vector spaces over finite fields. Let \(\mathbb{F}_q\) be the field with \(q = p^m\) elements.

Projective planes of order \(n\) exist for all prime powers \(n\). Whether non-prime-power orders are possible is the central open problem of projective geometry. The famous Bruck–Ryser theorem (1949), later extended by Chowla–Ryser, provides a necessary condition that eliminates many cases.

2.5 The Bruck–Ryser–Chowla Theorem

The proof uses the theory of rational quadratic forms and the Hasse–Minkowski theorem. The incidence matrix \(N\) of a symmetric design yields a quadratic form over \(\mathbb{Q}\): the form associated to \(N^TN = (k-\lambda)I + \lambda J\). The Hasse–Minkowski theorem requires this form to be equivalent (over all \(p\)-adic completions \(\mathbb{Q}_p\)) to the form on the right-hand side of the equation. When the local conditions fail — i.e., the equation has no \(p\)-adic solution for some prime \(p\) — no design exists.

For projective planes, \(\lambda = 1\) and the condition becomes: if \(n \equiv 1\) or \(2 \pmod{4}\), then \(n\) must be a sum of two squares. This eliminates \(n = 6\) (since \(6 \not\equiv 0, 3 \pmod 4\) and \(6\) is not a sum of two squares) and \(n = 14\). The non-existence of a projective plane of order 10 was proved by Lam, Thiel, and Swiercz (1989) using an exhaustive computer search — one of the largest computations in mathematics at the time.

The BRC theorem is illustrative of a general principle: existence questions for designs translate into questions about quadratic forms, and algebraic obstructions can prevent existence even when arithmetic conditions are met.

2.6 The Ray-Chaudhuri-Wilson Theorem

Fisher’s inequality \(b \geq v\) can be dramatically strengthened when additional intersection conditions are imposed. The Ray-Chaudhuri-Wilson theorem is one of the great achievements of algebraic combinatorics, giving a tight bound on the size of set families with prescribed intersection sizes.

Chapter 3: Orthogonal Latin Squares and Orthogonal Arrays

3.1 Latin Squares

A Latin square of order \(n\) is the combinatorial analogue of a multiplication table.

Latin squares are equivalent to one-dimensional block designs and encode the structure of quasigroups. The canonical example is the multiplication table of \(\mathbb{Z}_n\): entry \((i, j)\) is \(i + j \pmod{n}\).

The question of how many MOLS can exist of a given order \(n\) is one of the oldest problems in combinatorics, going back to Euler. The answer is now largely known, with a few stubborn small cases remaining.

3.2 Euler’s Conjecture and Its Refutation

The Euler conjecture (1782) stated that no pair of MOLS exists for \(n \equiv 2 \pmod{4}\). This was verified for \(n = 2\) (trivially) and \(n = 6\) (by exhaustive computation by Tarry in 1901), and remained open for nearly 180 years.

The conjecture was dramatically refuted by Bose, Shrikhande, and Parker in 1960:

The case \(n = 6\) (no pair of MOLS of order 6) was proved by Tarry’s exhaustive case analysis, with no known short proof. This is equivalent to the non-existence of a resolvable \(S(2, 3, 7)\) with a specific additional structure, and also to the non-existence of a projective plane of order 6.

The MacNeish conjecture (that \(N(n) = \min_i(p_i^{m_i}) - 1\) where \(n = \prod p_i^{m_i}\)) was also refuted by the Bose–Shrikhande–Parker construction.

3.3 Orthogonal Arrays

Latin squares are a special case of a broader combinatorial structure.

The parameter \(t\) is the strength, \(k\) is the number of constraints (rows), and \(n\) is the number of levels. The correspondence with Latin squares is:

• \(\mathrm{OA}(2, 3, n)\) ↔ Latin square of order \(n\): the three rows encode row index, column index, and entry.
• A set of \(m\) MOLS of order \(n\) ↔ \(\mathrm{OA}(2, m+2, n)\).

Orthogonal arrays arise in statistics (factorial experiments), coding theory (error-correcting codes), and cryptography (authentication codes). An \(\mathrm{OA}(t, k, n)\) is equivalent to a code with certain distance properties.

Chapter 4: Hadamard Matrices

4.1 Definition and Basic Properties

The rows of \(H\) form an equiangular frame: they are \(n\) vectors of norm \(\sqrt{n}\) in \(\mathbb{R}^n\) with all pairwise inner products equal to zero. Hadamard matrices are of great practical importance in signal processing, coding theory, and quantum information.

The Hadamard conjecture asserts that Hadamard matrices exist for all orders \(n \equiv 0 \pmod{4}\). This remains one of the major open problems in combinatorics. The smallest unresolved case was \(n = 668\) as of 2025.

4.2 Constructions

Sylvester’s construction (1867) produces Hadamard matrices of all powers-of-2 orders.

The resulting matrices are the Walsh–Hadamard matrices and are fundamental in signal processing (fast Walsh–Hadamard transform) and quantum computing (Hadamard gates).

The Paley construction, introduced by Raymond Paley in 1933, is the first non-trivial infinite family beyond powers of 2, and it reveals a deep connection between Hadamard matrices and number theory. The key observation is that the quadratic residues of a finite field \( \mathbb{F}_q \) split the nonzero elements into two equal halves — squares and non-squares — and this balanced partition automatically produces a matrix with the orthogonality properties needed for Hadamard. Heuristically: a Hadamard matrix needs every pair of distinct rows to agree on exactly half the columns and disagree on the other half; the Legendre symbol \( \chi(j-i) \) assigns \( \pm 1 \) to each pair according to whether their difference is a square in \( \mathbb{F}_q \), and the multiplicative structure of \( \mathbb{F}_q^* \) guarantees the required balance.

The Paley and Sylvester constructions together give Hadamard matrices of many orders. Various tensor product and “doubling” constructions extend the range further.

4.3 Hadamard Designs

One of the most important connections between Hadamard matrices and block designs is the following construction.

The Fano plane arises as the Hadamard design from \(H_8\) (the \(8 \times 8\) Walsh–Hadamard matrix). The Hadamard 3-designs are the closely related \(3\)-(4t, 2t, t-1) designs obtained from the full \(4t \times 4t\) Hadamard matrix.

Hadamard matrices and their associated designs are deeply connected to coding theory: the rows of a Hadamard matrix encode the codewords of a first-order Reed–Muller code, which achieves the best possible rate-distance trade-off for a binary code meeting the Plotkin bound.

Chapter 5: t-Designs and the Witt Designs

Everything in Chapters 1–4 dealt primarily with 2-designs (\( t = 2 \)) — structures where every pair of points appears in \( \lambda \) common blocks. These are already rich and difficult to classify. The natural generalization asks: what if every \( t \)-subset of points is covered exactly \( \lambda \) times? For \( t \geq 3 \), existence becomes dramatically more constrained and the known examples are far rarer. The most celebrated such examples are the Witt designs: the unique 4-(23, 7, 1) and 5-(24, 8, 1) designs, and their relatives, discovered by Ernst Witt in 1938. These designs are not just combinatorial curiosities — their automorphism groups are the Mathieu groups \( M_{22}, M_{23}, M_{24} \), the smallest of the 26 sporadic simple groups. The Witt designs thus sit at the intersection of combinatorial design theory and the classification of finite simple groups, making Chapter 5 a meeting point between the combinatorics of blocks and the deepest reaches of group theory.

5.1 Existence Questions for t-Designs

For \(t \geq 3\), the existence of \(t\)-designs with small \(\lambda\) is a delicate question. The necessary divisibility conditions for a \(t\)-(v, k, \lambda) design are that for each \(0 \leq s \leq t\),

For a long time, only finitely many non-trivial \(t\)-designs with \(t \geq 6\) and \(\lambda = 1\) were known. Wilson’s theorem resolved the asymptotic question completely.

Wilson’s theorem is one of the great achievements of combinatorics. However, it is existential and gives no bound on “sufficiently large.” The quest for small \(t\)-designs, especially with \(t \geq 5\) and small \(v\), requires very different techniques.

5.2 Derived and Residual Designs

Two operations on \(t\)-designs produce designs with smaller parameters.

These operations are key in proving uniqueness of designs: one shows that the derived and residual designs are unique (by induction on \(t\) or \(v\)), and then patches them together.

5.3 The Witt Designs

The most celebrated \(t\)-designs are the Witt designs, discovered by Ernst Witt in 1938. They are the unique \(5\)-designs with the parameters given below, and their automorphism groups are the Mathieu groups — some of the smallest and most mysterious sporadic simple groups.

The uniqueness of \(\mathcal{W}_{24}\) (proved by Witt) uses the derived/residual technique: one shows that derived designs at each step are unique, ultimately reducing to the uniqueness of the Fano plane. This chain of uniqueness results is a beautiful exercise in design theory.

The octads of \(\mathcal{W}_{24}\) encode deep structure: the Leech lattice \(\Lambda_{24}\) (the densest known sphere packing in \(\mathbb{R}^{24}\)) can be constructed from \(\mathcal{G}_{24}\), and the automorphism group of \(\Lambda_{24}\) is the Conway group \(Co_0\), which contains \(M_{24}\) as a subgroup.

5.4 Uniqueness and the Mathieu Groups

The Mathieu groups \(M_{11}, M_{12}, M_{22}, M_{23}, M_{24}\) were discovered by Émile Léonard Mathieu in 1861 and 1873 — the first sporadic simple groups to be found. Their rediscovery via the Witt designs in 1938 placed them on a firm combinatorial foundation.

Chapter 6: Association Schemes and Distance-Regular Graphs

6.1 Association Schemes

Association schemes provide a unified algebraic framework for studying distance-regular graphs, strongly regular graphs, and many families of combinatorial designs. The concept was introduced by Bose and Shimamoto (1952) in the context of statistical design of experiments.

The integers \(p^k_{ij}\) are the structure constants of the scheme. Notice \(p^0_{ij} = 0\) unless \(j = i\) (the “transpose” relation), and \(p^k_{00} = \delta_{0k}\).

6.2 The Bose–Mesner Algebra

The power of association schemes lies in their associated matrix algebra.

The Bose–Mesner algebra has a second distinguished basis: the minimal idempotents \(E_0, E_1, \ldots, E_d\), which satisfy \(E_i E_j = \delta_{ij} E_i\) and \(\sum_i E_i = I\). The change-of-basis matrices between \(\{A_i\}\) and \(\{E_j\}\) are the eigenvalue matrix \(P\) and its Krein-dual \(Q\):

The matrices \(P\) and \(Q\) play dual roles in the theory. The Delsarte linear programming bound uses \(Q\) to bound the size of codes and cliques in schemes.

6.3 Strongly Regular Graphs

The simplest non-trivial association schemes have \(d = 2\).

The adjacency matrix of an \(\mathrm{srg}(n,k,\lambda,\mu)\) satisfies the polynomial identity \(A^2 = kI + \lambda A + \mu(J - I - A)\), giving three eigenvalues \(k\) and \(r, s = \frac{(\lambda - \mu) \pm \sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}{2}\).

6.4 Distance-Regular Graphs

Setting \(a_i = k - b_i - c_i\) (the number of neighbours at the same distance), we get \(A^2\) and higher powers of \(A\) expressible in terms of the tridiagonal recurrence given by the intersection array. This gives a \((D+1)\)-class association scheme.

Distance-regular graphs arise as coset graphs of codes, orbital graphs of permutation groups, and geometries. The Delsarte–Goethals–Seidel bound on the size of codes in Johnson schemes connects designs to distance-regular graphs in a fundamental way.

6.5 Delsarte’s Linear Programming Bound

The Bose–Mesner algebra and the \(Q\)-matrix lead to Delsarte’s celebrated bound.

Delsarte’s LP bound (1973) unified and improved previously known bounds on error-correcting codes, and its dual gives lower bounds on designs (the “Fisher-type” bound on the number of blocks, and later the absolute bound on equiangular lines). It is a cornerstone of algebraic combinatorics.

Chapter 7: Lines, Spherical Designs, and Mutually Unbiased Bases

7.1 Equiangular Lines

Sets of equiangular lines are equivalent to certain association schemes, and their study connects design theory to spectral graph theory and quantum information. The Gram matrix \(G_{ij} = \langle u_i, u_j \rangle\) (where we choose unit vectors \(u_i\) for each line, choosing the sign to make the Gram matrix as uniform as possible) satisfies a polynomial equation constraining the spectrum of \(G\), which in turn bounds \(m\).

The problem of determining the maximum number of equiangular lines in \(\mathbb{R}^d\) for all \(d\) is currently active research. Bukh (2016) and Lin–Yu (2020) proved asymptotic bounds; the exact answer is known for small \(d\) and for specific infinite families.

7.2 Spherical Designs

Spherical designs generalise the notion of a design from finite sets to the unit sphere, providing a framework for numerical integration that is exact for polynomials up to a given degree.

In other words, \(X\) is a spherical \(t\)-design if and only if the average of every harmonic polynomial of degree at most \(t\) over \(X\) is zero. This is the continuous analogue of the discrete uniformity condition in a \(t\)-design.

Tight spherical designs are the analogues of Steiner systems in the spherical setting. They are rare and beautiful: examples include the vertices of the regular simplex (tight 2-design in \(S^{d-1}\)), the vertices of the regular icosahedron (tight 5-design in \(S^2\)), and the minimal vectors of the \(E_8\) lattice (a tight 7-design on \(S^7\) with 240 points).

7.3 Mutually Unbiased Bases

Mutually unbiased bases (MUBs) arise in quantum mechanics as measurement bases that are maximally incompatible: measuring in one basis gives no information about the outcome of measuring in the other.

Whether \(d+1\) MUBs exist in \(\mathbb{C}^d\) for non-prime-power \(d\) is a major open question in quantum information theory. The smallest unresolved case is \(d = 6\): it is unknown whether 7 MUBs exist in \(\mathbb{C}^6\). Numerical and algebraic evidence strongly suggests the answer is no (only 3 MUBs are known), but no proof exists.

7.4 Complex Equiangular Lines and SIC-POVMs

In \(\mathbb{C}^d\), the analogue of equiangular lines is SIC-POVMs (symmetric informationally complete positive operator-valued measures) — a concept from quantum information theory.

SIC-POVMs are the complex analogues of tight spherical 2-designs in \(\mathbb{C}^d\). They achieve the absolute bound \(d^2\) for equiangular lines in \(\mathbb{C}^d\).

Zauner’s conjecture connects to deep number theory (class field theory over real quadratic fields), and understanding it is one of the outstanding open problems bridging quantum information and pure mathematics. Godsil’s course treats this from the perspective of complex Hadamard matrices and association schemes.

7.5 Hadamard Matrices and Quantum Information

The connection between Hadamard matrices and quantum information theory runs deep. The Walsh-Hadamard transform is the quantum Fourier transform over \(\mathbb{Z}_2^n\), and real Hadamard matrices correspond to unitary designs.

7.5 Connections and the Broader Picture

The objects studied in this course are deeply interconnected:

The unifying theme throughout is the interplay between regularity (uniformity conditions on combinatorial structures), linear algebra (eigenvalue methods, Gram matrices, quadratic forms), and geometry (finite projective spaces, spheres, lattices). Godsil’s approach in Geometry: Finite, Real, Imaginary is to see all these objects as special cases of a geometric philosophy: finite analogues of the great continuous geometries of Euclidean and projective space.

7.6 Open Problems and Future Directions

Combinatorial design theory is a field with a wealth of open problems at all levels of difficulty. We close with a brief survey of the major open questions.

Appendix: Key Notation and Parameter Summary

Chapter 8: Difference Sets and Cyclic Designs

8.1 The Concept of a Difference Set

Among all methods for constructing block designs, the theory of difference sets is at once the most elegant and the most powerful. It reduces the problem of building a design with the right intersection structure to a purely group-theoretic condition, turning combinatorics into number theory.

The name comes from the original setting of cyclic groups \(G = \mathbb{Z}_v\): the “differences” are \(d_i - d_j \pmod{v}\) for \(d_i \neq d_j \in D\). The condition that each nonzero difference appears exactly \(\lambda\) times is the key regularity property.

The connection to design theory is immediate: if \(D \subseteq G\) is a \((v,k,\lambda)\)-difference set, then the development of \(D\) — the collection of translates \(\{D + g : g \in G\}\) — forms a symmetric \((v, k, \lambda)\)-design. Each translate is a block, and the regularity condition on differences guarantees that any two points appear together in exactly \(\lambda\) blocks.

8.2 Singer’s Theorem and Planar Difference Sets

The most important family of difference sets comes from finite projective geometry. A Singer cycle is a cyclic group that acts regularly on the points of a projective space.

For \(d = 2\), this gives a \((q^2+q+1,\, q+1,\, 1)\)-difference set — the planar difference set corresponding to the Desarguesian projective plane \(\mathrm{PG}(2,q)\).

The Singer construction is foundational because it shows that the “combinatorial” structure of a projective plane is completely captured by a single cyclic group element. This is why Hamming codes (whose parity check matrices are constructed from Singer cycles) have such elegant structure.

8.3 Multipliers and the Hall-Paige Condition

The multiplier theorem is a powerful tool for proving uniqueness of difference sets.

The multiplier theorem gives a way to show that a potential difference set (if it exists) must be invariant under multiplication by \(p\). This greatly restricts the search space for difference sets and is used to prove non-existence: if the multiplier group acts on the potential difference set in a way inconsistent with the required parameters, then the difference set cannot exist.

8.4 Hadamard Difference Sets

A \((v, k, \lambda)\)-difference set with \(v = 4\mu\), \(k = 2\mu - 1\), \(\lambda = \mu - 1\) (so \(k - \lambda = \mu\)) is called a Hadamard difference set or \((4\mu-1, 2\mu-1, \mu-1)\)-difference set. Its development gives a Hadamard design — a symmetric \((4\mu-1, 2\mu-1, \mu-1)\)-design, which is the “residual” of a Hadamard matrix.

Chapter 9: Resolutions and Parallelisms

9.1 Resolvable Designs

A resolution of a design adds further structure: it partitions the blocks into “parallel classes,” each class itself forming a partition of the point set. This concept has classical roots in Kirkman’s 1847 schoolgirl problem.

For a resolvable \((v, k, 1)\)-design (a Steiner system \(S(2, k, v)\)), each parallel class has exactly \(v/k\) blocks, and the number of parallel classes is \(r = \lambda(v-1)/(k-1) = (v-1)/(k-1)\). The necessary condition for resolvability is \(k \mid v\).

9.2 Ray-Chaudhuri-Wilson Theorem

The Ray-Chaudhuri-Wilson theorem (1971) is the definitive resolvability result for Steiner triple systems:

The necessity is arithmetic: \(v \equiv 1\) or \(3 \pmod 6\) is needed for an STS to exist; the extra condition \(v \equiv 3 \pmod 6\) (not \(v \equiv 1\)) ensures that 3 divides \(v\), which is required for each parallel class to partition all \(v\) points into groups of 3.

The sufficiency proof is constructive: for any \(v \equiv 3 \pmod 6\), one constructs an explicit resolvable STS using a “direct” construction (algebraic methods over \(\mathbb{Z}_v\) for prime \(v\)) and a “recursive” construction (combining smaller resolvable STSs into larger ones via product constructions).

9.3 The Existence Theorem for Resolvable Designs

Wilson’s asymptotic existence theorem (1975) extends the Rödl nibble packing result to a sharp statement:

The proof uses the theory of transversals in Latin squares (essentially, a large “balanced” Latin square can be resolved into subsquares) combined with a direct counting argument. Wilson’s theorem was a landmark: it showed that the necessary conditions for the existence of a resolvable design are (asymptotically) also sufficient, mirroring the pattern for non-resolvable designs established by the same author.

9.4 Room Squares

A Room square of order \(2n\) (named after Thomas Room, 1955) is a symmetric Latin square of order \(2n-1\) with special structure: a \((2n-1) \times (2n-1)\) array where each cell contains either a pair \(\{i,j\} \subseteq \{1, \ldots, 2n\}\) or is empty, such that:

• Each of the \(2n\) symbols appears in exactly one cell per row and one cell per column.
• Each pair \(\{i,j\}\) appears in exactly one cell.

Room squares generalize to starter-adder constructions over cyclic groups, which provide a unified framework for tournament scheduling, round-robin tournaments, and other combinatorial designs with rotational symmetry. They are equivalent to 1-factorizations of complete graphs, connecting design theory to graph theory.

Chapter 10: Codes from Designs

10.1 The Code of a Design

Every design has a natural associated linear code, obtained by viewing the incidence matrix over a finite field.

The parameters of \(C_p(\mathcal{D})\) — its length \(n = b\), its dimension \(k = \mathrm{rank}_p(N)\), and its minimum distance \(d\) — carry deep information about the design. In particular:

• The minimum distance of \(C_p(\mathcal{D})\) is related to the minimum number of blocks needed to cover all points an odd number of times.
• The dual code \(C_p(\mathcal{D})^\perp\) is often the code of a complementary or “derived” design.

10.2 Reed-Muller Codes from Affine Geometry

The Reed-Muller codes are among the most important codes in both theory and practice. They arise naturally from the geometry of affine spaces.

The parameters of \(\mathcal{R}(r, m)\) are:

The connection is deep: the weight enumerator of a Reed-Muller code can be computed from the design-theoretic parameters of the associated hyperplane design, and vice versa. The Assmus-Mattson theorem (1969) formalizes this: certain codes automatically contain designs among their minimum-weight codewords.

10.3 The MacWilliams Transform

If \(C\) is a linear code with weight enumerator \(W_C(x, y) = \sum_{w} A_w x^{n-w} y^w\), then the weight enumerator of the dual code \(C^\perp\) is determined by the MacWilliams transform:

This formula has a clean interpretation: the weight distribution of the dual code is the Krawtchouk (discrete Fourier) transform of the weight distribution of the original code. It is the discrete analogue of the Poisson summation formula.

10.4 The Assmus-Mattson Theorem

The Assmus-Mattson theorem (1969) gives a systematic way to extract designs from codes.

The theorem is used to prove, for example, that the weight-8 codewords of the Golay code \(\mathcal{G}_{24}\) form the Witt design \(5-(24, 8, 1)\) — indeed, the Assmus-Mattson theorem applied to \(\mathcal{G}_{24}\) gives \(t = 5\), consistent with the 5-design structure. Similarly, the weight-12 codewords of the ternary Golay code \(\mathcal{G}_{12}\) form the small Witt design \(5-(12, 6, 1) = \mathcal{W}_{12}\). This beautiful correspondence — codes determine designs, and designs determine codes — is the unifying theme of Assmus and Key’s monograph.

10.5 The Sphere-Covering and Sphere-Packing Bounds

The design-theoretic parameters of a code are constrained by two classical bounds.

A code achieving equality in the Hamming bound is called perfect. Perfect binary codes are fully classified: the only nontrivial ones are the Hamming codes \([2^r - 1, 2^r - r - 1, 3]\) and the Golay code \([23, 12, 7]\). This classification (Lloyd 1957, van Lint-Tietäväinen 1973) is one of the deepest results in coding theory, and it provides a characterization of the Hamming and Golay designs in purely coding-theoretic terms.

Chapter 11: The Linear Algebra Bound and Fisher-Type Inequalities

11.1 Ray-Chaudhuri-Wilson and the Absolute Bound

The most powerful bounds in design theory come from linear algebra. The general philosophy is: embed the blocks (or points) of a design as vectors in a vector space, then use the rank of the resulting matrix to bound the number of vectors.

The RCW theorem is a vast generalization of Fisher’s inequality (which is the case \(s = 1, L = \{\lambda\}\)) and the Delsarte-Goethals-Seidel bound. Its specializations give the best-known bounds on:

• Two-distance sets in \(\mathbb{R}^n\): at most \(\binom{n+2}{2}\) points.
• \(s\)-distance sets (sets where all pairwise distances take only \(s\) values): at most \(\binom{n+s}{s}\) points.
• Equiangular lines: at most \(\binom{n+1}{2}\) lines (the absolute bound from Chapter 7).

11.2 Oddtown and Eventown

The “oddtown/eventown” results are elegant applications of the linear algebra method to purely combinatorial problems.

These results have become the prototypical examples of the linear algebra method in combinatorics — a collection of techniques where one assigns vectors to combinatorial objects and uses linear independence to bound their number. The method is closely related to the Delsarte LP bound: both exploit the fact that objects with limited intersection structure must be “nearly orthogonal.”

11.3 The Frankl-Wilson Theorem

The Frankl-Wilson theorem combines the linear algebra method with the Ray-Chaudhuri-Wilson theorem to give striking bounds in discrete geometry.

The most spectacular application is the chromatic number of the unit-distance graph. Let \(G_n\) be the graph on \(\{0,1\}^n\) where two vectors are adjacent if their Hamming distance is exactly \(n/2\) (for even \(n\)). Frankl and Wilson show \(\chi(G_n) \geq (1.2)^n\) by the modular intersection bound. More dramatically: the chromatic number of \(\mathbb{R}^n\) (the Hadwiger-Nelson-type problem in higher dimensions) satisfies \(\chi(\mathbb{R}^n) \geq (1.2389...)^n\), proved by the Frankl-Wilson construction of a set in \(\{0,1\}^n\) with no two points at distance 1 whose chromatic number forces many colors.

Chapter 12: Sharply Transitive Sets and the Cayley Graph Connection

12.1 Group Actions on Designs

The automorphism group of a design acts on both its point set and block set. The interplay between a design’s symmetry group and its combinatorial structure is one of the deepest themes in the subject. When the automorphism group acts transitively — or even sharply transitively — on points, blocks, or flags, the design acquires an algebraic structure that greatly simplifies both construction and analysis.

Flag-transitive designs are precisely those for which every point-block pair \((p, B)\) looks the same — a very strong symmetry condition. The classification of flag-transitive 2-designs is a major open problem, with progress tied to the classification of finite simple groups (CFSG). Using CFSG, O’Nan and Scott (1980) and later Buekenhout (1990) gave a partial classification of flag-transitive designs.

12.2 Cayley Graphs and Difference Sets

Every difference set \(D\) in a group \(G\) defines a Cayley graph \(\mathrm{Cay}(G, D - D^{-1})\) where two group elements \(g, h\) are adjacent iff \(gh^{-1} \in D \cup D^{-1}\). This graph is strongly regular when \(D\) is a \((v, k, \lambda)\)-difference set.

The Paley graph \(P(q)\) for a prime power \(q \equiv 1 \pmod 4\) is the Cayley graph \(\mathrm{Cay}(\mathbb{F}_q, Q)\) where \(Q\) is the set of nonzero quadratic residues. Since \(|Q| = (q-1)/2\), the Paley graph is a conference graph — it is a self-complementary strongly regular graph with parameters \((q, (q-1)/2, (q-5)/4, (q-1)/4)\). The Paley graphs are the canonical examples of Ramsey graphs: by the second-moment method, the clique and independence numbers of \(P(q)\) are both \(O(\sqrt{q} \log q)\), giving the largest known explicit constructions avoiding large cliques or independent sets.

12.3 Planar Functions and Semifields

A planar function over \(\mathbb{F}_q\) (for odd prime power \(q\)) is a function \(f: \mathbb{F}_q \to \mathbb{F}_q\) such that the map \(x \mapsto f(x+a) - f(x)\) is a bijection for every nonzero \(a \in \mathbb{F}_q\). Planar functions generalize difference sets to the non-abelian setting.

More exotic planar functions (like \(f(x) = x^{(3^k+1)/2}\) over \(\mathbb{F}_{3^n}\) for appropriate \(k, n\)) give rise to non-Desarguesian projective planes — planes that cannot be coordinatized by a field but only by a semifield (a division ring that may not satisfy associativity of multiplication). The classification of semifields, and hence of non-Desarguesian planes, remains an active research area.

12.4 The Polynomial Method for Designs

Polynomial methods, developed in Chapter 13 of CO 448 (Combinatorial Nullstellensatz), also apply to design theory. The cleanest application is the proof of Wilson’s theorem via the permanent of a polynomial matrix.

12.5 Concluding Perspective

The three strands woven throughout this course — linear algebra, finite geometry, and probabilistic/algebraic combinatorics — converge at the deepest results. Fisher’s inequality and the Delsarte LP bound use linear algebra to constrain parameters. Projective planes and difference sets use finite field arithmetic to provide constructions. The Witt designs and Golay codes exist at the intersection of all three, requiring group theory (Mathieu groups), coding theory (Golay codes), and algebraic combinatorics (association schemes) for a complete understanding.

The field continues to develop rapidly. Recent breakthroughs — Keevash’s existence theorem for designs (2014), the resolution of the Existence Conjecture for resolvable designs (Glock-Kühn-Lo-Osthus, 2020), and progress on Zauner’s conjecture via class field theory (Appleby et al., 2017) — show that the classical questions of design existence, uniqueness, and structure are far from exhausted. The interaction between high-powered algebraic machinery (representation theory, algebraic number theory) and elementary combinatorial structure (intersection numbers, regularity) remains the defining feature of the subject.

Appendix B: Notable Designs and Their Parameters

The following table collects the most important specific designs appearing in the course.

The Mathieu groups \(M_{11}, M_{12}, M_{22}, M_{23}, M_{24}\) are the first five sporadic simple groups discovered and arise as automorphism groups of the Witt designs. Their existence is intimately tied to the richness of the Golay codes: the Golay codes are uniquely characterized by being the only doubly-even self-dual binary codes of their parameters, and this uniqueness forces the automorphism group to be extremely large.