Block Design

An incidence system ($v$, $k$, $\lambda$, $r$, $b$) in which a set $X$ of $v$ points is partitioned into a family $A$ of $b$ subsets (blocks) in such a way that any two points determine $\lambda$ blocks with $k$ points in each block, and each point is contained in $r$ different blocks. It is also generally required that $k<v$, which is where the ``incomplete'' comes from in the formal term most often encountered for block designs, Balanced Incomplete Block Designs (BIBD). The five parameters are not independent, but satisfy the two relations

$$vr=bk$$ (1)

$$\lambda(v-1)=r(k-1).$$ (2)

A BIBD is therefore commonly written as simply ($v$, $k$, $\lambda$), since $b$ and $r$ are given in terms of $v$, $k$, and $\lambda$ by

$$b = {v(v-1)\lambda\over k(k-1)}$$ (3)

$$r = {\lambda(v-1)\over k-1}.$$ (4)

A BIBD is called Symmetric if $b=v$ (or, equivalently, $r=k$).

Writing $X=\{x_i\}_{i=1}^v$ and $A=\{A_j\}_{j=1}^b$, then the Incidence Matrix of the BIBD is given by the $v\times b$ Matrix ${\hbox{\sf M}}$ defined by

$$m_{ij}=\cases{ 1 & if $x_i\in A$\cr 0 & otherwise.\cr}$$ (5)

This matrix satisfies the equation

$${\hbox{\sf M}}{\hbox{\sf M}}^{\rm T}=(r-\lambda){\hbox{\sf I}}+\lambda{\hbox{\sf J}},$$ (6)

where ${\hbox{\sf I}}$ is a $v\times v$ Identity Matrix and ${\hbox{\sf J}}$ is a $v\times v$ matrix of 1s (Dinitz and Stinson 1992).

Examples of BIBDs are given in the following table.

Block Design	($v$, $k$, $\lambda$)
Affine Plane	($n^2$, $n$, 1)
Fano Plane	(7, 3, 1))
Hadamard Design	Symmetric ($4n+3$, $2n+1$, $n$)
Projective Plane	Symmetric ($n^2+n+1$, $n+1$, 1)
Steiner Triple System	($v$, 3, 1)
Unital	($q^3+1$, $q+1$, 1)

See also Affine Plane, Design, Fano Plane, Hadamard Design, Parallel Class, Projective Plane, Resolution, Resolvable, Steiner Triple System, Symmetric Block Design, Unital

References

Dinitz, J. H. and Stinson, D. R. ``A Brief Introduction to Design Theory.'' Ch. 1 in Contemporary Design Theory: A Collection of Surveys (Ed. J. H. Dinitz and D. R. Stinson). New York: Wiley, pp. 1-12, 1992.

Ryser, H. J. ``The $(b, v, r, k, \lambda)$-Configuration.'' §8.1 in Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 96-102, 1963.