info prev up next book cdrom email home

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

\begin{displaymath}
vr=bk
\end{displaymath} (1)


\begin{displaymath}
\lambda(v-1)=r(k-1).
\end{displaymath} (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
$\displaystyle b$ $\textstyle =$ $\displaystyle {v(v-1)\lambda\over k(k-1)}$ (3)
$\displaystyle r$ $\textstyle =$ $\displaystyle {\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

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

This matrix satisfies the equation
\begin{displaymath}
{\hbox{\sf M}}{\hbox{\sf M}}^{\rm T}=(r-\lambda){\hbox{\sf I}}+\lambda{\hbox{\sf J}},
\end{displaymath} (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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26