Introduction to Combinatorics, 2nd Edition

CHAPTER 6

COMBINATORIAL DESIGNS

The Fano Configuration FC is the simplest nontrivial example of many types of combinatorial configurations, including t-designs, Steiner systems, block designs, and projective planes. We next explore these designs and investigate their interconnections, paving the way for the construction of the Golay code G₂₃, the only perfect binary code capable of correcting more than one error, and Leech’s remarkable 24-dimensional lattice.

6.1 t-designs

A t-(v, k, λ) design (or t-design) consists of a v-set S and a collection C of k-subsets of S, with the property that every t-subset of S is contained in exactly λ members of C. The elements of S are called points and the elements of C are called blocks.

A t-design is nontrivial if 0 < t < k < v and not every k-subset of S is a block.

EXAMPLE 6.1

The lines 246, 167, 145, 257, 123, 347, and 356 of FC are the blocks of a 2-(7, 3, 1) design with S = {1,…,7}.

EXAMPLE 6.2

The complement FC’ of FC has the same set of vertices as FC. Its lines are the complements of the lines of FC: 1357, 2345, 2367, 1346, 4567, 1256, 1247. It is easy to verify that the lines of FC’ constitute the blocks of a 2-(7, 4, 2) design.

EXAMPLE ...