Block Designs

We will now begin to look at a very interesting type of structure known as a block design. We begin by stating the definition of a block design.

Definition: Let $X$ be a set and let $\mathcal A$ be a multiset of nonempty subsets of $X$. The pair $(X, \mathcal A)$ is a Block Design on $X$.

It is standard to call the elements of $X$ "points" and the elements of the multiset $\mathcal A$, "blocks" or "lines".

The definition of a block design above is not restrictive and we can define less general block designs by requiring that a block design has additional properties. For example, since $\mathcal A$ is a multiset - we allow for elements in $\mathcal A$ to be repeated. In some contexts, we may look at block designs for which every element in $\mathcal A$ is distinct. We define such block designs below.

Definition: A block design $(X, \mathcal A)$ is a Simple Block Design on $X$ if $\mathcal A$ contains no repeated blocks.

Another common type of block design that will be of relevance are define below.

Definition: Let $X$ be a finite set, and let $v$, $k$, and $\lambda$ be positive integers for which $2 \leq k < v$. A $(v, k, \lambda)$-Balanced Incomplete Block Design is a block design $(X, \mathcal A)$ such that: 1) $\mid X \mid = v$. 2) Every block in $\mathcal A$ contains exactly $k$ points, i.e., for all $A \in \mathcal A$, $\mid A \mid = k$. 3) Every pair of distinct points in $X$ is contained in exactly $\lambda$ blocks, i.e., for all $x, y \in X$ with $x \neq y$ there exists exactly $\lambda$ blocks, $A_1, A_2, ..., A_{\lambda} \in A$ for which both $x \in A_1, A_2, ..., A_{\lambda}$ and $y \in A_1, A_2, ..., A_{\lambda}$.

We often use the abbreviation "$(v, k, \lambda)$-BIBD" to denote a $(v, k, \lambda)$-balanced incomplete block design.

Perhaps the nicest example of a BIBD occurs in the construction of the famous Fano plane.

Consider the following set of integers:

(1)

\begin{align} \quad X = \{ 1, 2, 3, 4, 5, 6, 7 \} \end{align}

The elements in $X$ will be referred to as "points" to be consistent with the definition above. Let $\mathcal A$ be the following set:

(2)

\begin{align} \quad \mathcal A = \{ \{ 1,2,3 \}, \{ 3,4,5 \}, \{ 5, 6, 1 \}, \{1, 7, 4\}, \{ 2, 7, 5 \}, \{ 3, 7, 6 \}, \{ 2, 4, 6 \} \} \end{align}

The elements in $\mathcal A$ will be referred to as "lines". Then $(X, \mathcal A)$ is a block design. Furthermore, it is a $(7, 3, 1)$-BIBD. This is because $\mid X \mid = 7$, every block in $\mathcal A$ contains $3$ points, and it can be easily verified that every pair of points in $X$ occur in only one block in $\mathcal A$. This $(7, 3, 1)$-BIBD can also be represented nicely with the following diagram:

This diagram is often referred to as the Fano plane and is actually what is referred to as a finite projective plane (we will look at these later).