Balanced Incomplete Block Designs

Recall from the Block Designs page that if $X$ is a set and $\mathcal A$ is a multiset of nonempty subsets of $X$ then the pair $(X, \mathcal A)$ is called a block design on $X$.

We then define some special types of block designs. One type of block design of significance that we looked at briefly were Balanced Incomplete Block Designs (BIBDs). Recall that if $X$ is a finite set and $v$, $k$, and $\lambda$ are positive integers for which $2 \leq k < v$ then a $(v, k, \lambda)$-balanced incomplete block design is a block design $(X, \mathcal A)$ for which:

• 1. $\mid X \mid = v$.

• 2. Every block in $\mathcal A$ contains exactly $k$ points, that is, for all $A \in \mathcal A$ we have that $\mid A \mid = k$.

• 3. Every pair of distinct points in $X$ occur in exactly $\lambda$ blocks, that is, for all $x, y \in X$ with $x \neq y$ there exists exactly $\lambda$ blocks $A_1, A_2, ..., A_{\lambda}$ for which $x \in A_1, A_2, ..., A_{\lambda}$ and $y \in A_1, A_2, ..., A_{\lambda}$.

We will now look further into BIBDs by first giving a theorem which allows us to construct a very simple class of BIBDs.

Theorem 1: Let $v$ and $k$ be positive integers such that $2 \leq k < v$. If $X$ is a set containing $v$ elements and $\mathcal A$ is the collection of all $k$-element subsets of $X$ then $(X, \mathcal A)$ is a $\displaystyle{\left (v, k, \binom{v-2}{k-2} \right )}$-BIBD.

• Proof: Since $X$ contains $v$ elements, $\mid X \mid = v$.

• Furthermore, every block in $\mathcal A$ by definition has $k$ points.

• All that remains to show is that every pair of distinct points in $X$ occur in exactly $\displaystyle{\binom{v-2}{k-2} = \frac{(v - 2)!}{([v - 2] - [k - 2])! (k - 2)!} = \frac{(v - 2)!}{(v - k)!(k - 2)!}}$ blocks.

• Now the number of $k$-subsets of a $v$-element set is $\displaystyle{\binom{v}{k} = \frac{v!}{(v - k)! k!}}$. Let $x, y \in X$ be such that $x \neq y$. Then the number of $k$-subsets for which $x$ is contained in is equal to the number of $k$-subsets multiplied by the number of elements in each $k$-subset and divided by the number of elements in $X$, that is, $x$ appears in exactly $\displaystyle{\frac{v!}{(v - k)!k!} \cdot \frac{k}{v} = \frac{(v-1)!}{(v - k)!k!}}$ blocks.

• We now look at the $\displaystyle{ \frac{(v-1)!}{(v - k)!k!}}$ blocks containing $x$. We want to count the number of these blocks which also contain $y$. This is equal to the number of blocks containing $x$ multiplied by the size of these blocks excluding the element $x$ and divided by the number of elements in $X$ excluding the element $a$, that is, $y$ appears in exactly $\displaystyle{\frac{(v-1)!}{(v - k)!(k - 1)!} \cdot \frac{(k - 1)}{(v - 1)} = \frac{(v - 2)!}{(v - k)!(k - 2)!} = \binom{v - 2}{k - 2}}$ of these blocks.

• Hence every pair of distinct points $x, y \in X$ with $x \neq y$ occur in exactly $\displaystyle{\binom{v - 2}{k - 2}}$ blocks. So $(X, \mathcal A)$ is a $\displaystyle{\left ( v, k, \binom{v - 2}{k-2} \right )}$-BIBD. $\blacksquare$

For example, suppose that we want to construct a BIBD on the set $X = \{ 1, 2, 3, 4, 5 \}$. By Theorem 1, we can construct, say a $\left ( 5, 3, \binom{3}{1} \right ) = (5, 3, 3)$-BIBD $(X, \mathcal A)$ where:

(1)

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

Notice that $\mid X \mid = 5$, every block in $\mathcal A$ contains $k = 3$ elements, and every pair of distinct points in $X$ is contained in exactly $3$ blocks. So, indeed $(X, \mathcal A)$ is a $(5, 3, 3)$-BIBD.