Combinatorial Designs - Core Definitions

Combinatorial designs are structured arrangements of elements satisfying specific balance and symmetry properties. They arise in experimental design, coding theory, and finite geometry, providing optimal arrangements for various applications.

DefinitionBlock Design

A block design is a pair $(V, \mathcal{B})$ where $V$ is a set of $v$ points (or varieties) and $\mathcal{B}$ is a collection of $b$ blocks (subsets of $V$ ).

A $t$ - $(v, k, \lambda)$ design has the properties:

Each block contains exactly $k$ points ( $|B| = k$ for all $B \in \mathcal{B}$ )
Every $t$ -subset of $V$ appears in exactly $\lambda$ blocks

When $t = 2$ , we call it a balanced incomplete block design (BIBD) or 2-design, often denoted $2$ - $(v, k, \lambda)$ .

The "balanced" property ensures uniform distribution: every pair of points appears together the same number of times.

ExampleFano Plane

The Fano plane is a $2$ - $(7, 3, 1)$ design:

7 points: $V = \{1, 2, 3, 4, 5, 6, 7\}$
7 blocks (lines): $\{\{1,2,4\}, \{2,3,5\}, \{3,4,6\}, \{4,5,7\}, \{5,6,1\}, \{6,7,2\}, \{7,1,3\}\}$

Every pair of points appears in exactly one block. This is the smallest non-trivial projective plane.

DefinitionLatin Square

A Latin square of order $n$ is an $n \times n$ array filled with $n$ different symbols such that each symbol appears exactly once in each row and exactly once in each column.

Two Latin squares are orthogonal if, when superimposed, each ordered pair of symbols appears exactly once.

Example3×3 Latin Squares

\begin{array}{|c|c|c|} \hline A & B & C \\ \hline B & C & A \\ \hline C & A & B \\ \hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 3 & 1 & 2 \\ \hline 2 & 3 & 1 \\ \hline \end{array}

These are orthogonal: superimposing gives all 9 ordered pairs (A,1), (A,2), ..., (C,3) exactly once.

DefinitionSteiner System

A Steiner system $S(t, k, v)$ is a $t$ - $(v, k, 1)$ design (where $\lambda = 1$ ): every $t$ -subset appears in exactly one block.

Famous examples:

$S(2, 3, 7)$ : Fano plane
$S(2, 3, 9)$ : Affine plane of order 3
$S(5, 8, 24)$ : Related to the binary Golay code and the Mathieu group $M_{24}$

Remark

Combinatorial designs originated in agricultural experiments (R.A. Fisher, 1920s-1930s) to efficiently test treatments while controlling for variation. Fisher developed BIBD theory to minimize the number of experimental plots while maintaining statistical balance. Today, designs appear in tournament scheduling (every pair of teams plays exactly once), error-correcting codes (Hadamard matrices, Golay codes), cryptography (key distribution schemes), and finite geometry. The existence and construction of designs with given parameters remains an active research area, with deep connections to algebra, number theory, and graph theory.

These structured arrangements provide optimal solutions to resource allocation and experimental design problems.