Combinatorial design theory ($t\text{-}(v,k,\lambda )$)

Combinatorial design theory studies finite incidence patterns in which prescribed small collections occur equally often. A $t$-$(v,k,\lambda )$ combinatorial design consists of $v$ points and blocks of size $k$, with every $t$-element subset of points in exactly $\lambda$ blocks. Counting incidences between blocks and their $t$-element subsets giveswhere $b$ is the number of blocks.^[ref]

On $\{1,2,3,4\}$, take all four three-element subsets as blocks. Each pair occurs twice, so this is a $2$-$(4,3,2)$ combinatorial design; the count is $4\cdot 3=2\cdot 6$. These exact balance conditions turn questions about fair comparisons and repeated pairings into existence, construction and counting problems. The displayed divisibility condition is necessary, but does not by itself ensure that a design exists.

In the point-block convention, an incidence structure consists of a set $P$ of points, a set $B$ of blocks, and a relation $I\subseteq P\times B$ specifying which points lie on which blocks. Blocks are abstract objects: distinct blocks may have identical sets of incident points unless a simplicity condition forbids this. A finite incidence structure is encoded by its incidence matrix of a set system, with entry $1$ for incidence and $0$ otherwise.

For example, take points $1,2,3$ and three blocks incident with $\{1,2\}$, $\{2,3\}$ and $\{1,3\}$. With points indexing rows, the incidence matrix of a set system isEvery point lies on two blocks, every block contains two points, and every pair of distinct points lies on exactly one block. It is a $2$-$(3,2,1)$ combinatorial design. Its matrix rank is three over $\mathbb{Q}$ but two over ${\mathbb{F}}_2$, since its determinant is two. This illustrates why incidence and the coefficient field jointly matter in algebraic counting arguments.

Finite geometries, graphs and combinatorial designs all supply incidence structures, but additional axioms distinguish their particular classes. Merely specifying incidence does not require any balanced-design or projective-plane axioms. Typed incidence structures can include further element types, such as points, lines and planes.^[ref]

A $t$-$(v,k,\lambda )$ combinatorial design is an incidence structure on $v$ points with blocks containing $k$ points, such that every $t$-element subset lies in exactly $\lambda$ blocks. Repeated blocks may be allowed; a simple design has no repetitions. With $b$ blocks, counting pairs consisting of a block and one of its $t$-subsets givesFor a two-design, each point lies in $r=\lambda (v-1)/(k-1)$ blocks.^[ref]

The seven triples $123,145,167,246,257,347,356$ on $\{1,\dots ,7\}$ form a $2$-$(7,3,1)$ design: every pair occurs once, and every point occurs three times. This is the Fano plane. The equation checks $7\cdot 3=1\cdot 21$. Such exact incidence balance makes combinatorial designs useful for arranging comparisons and constructing highly symmetric finite structures.