The Complement Construction of Balanced Incomplete Block Designs

On The Sum Construction of Balanced Incomplete Block Designs page we saw that if $(X, \mathcal A_1)$ is a $(v, k, \lambda_1)$-BIBD and $(X, \mathcal A_2)$ is a $(v, k, \lambda_2)$-BIBD then $(X, \mathcal A)$ where $\mathcal A$ is the multiset union of $\mathcal A_1$ and $\mathcal A_2$ is a $(v, k, \lambda_1 + \lambda_2)$-BIBD.

We now obtain another method to construct a new BIBD from an old BIBD in terms of taking the new blocks to be the complementary sets of the old blocks.

Theorem 1: Let $(X, \mathcal A)$ be a $(v, b, r, k, \lambda)$-BIBD and that $k \leq v - 2$. Then $(X, \{ X \setminus A : A \in \mathcal A \}$ is a $(v, b, b - r, v - k, b - 2r + \lambda)$-BIBD.

• Proof: The pair $(X, \{ X \setminus A : A \in \mathcal A \})$ has point set $X$ and block set $\{ X \setminus A : A \in \mathcal A \}$. By definition there are $v$ points in $X$.

• It is not hard to see that as $A$ ranges through $\mathcal A$ we obtain a corresponding complement set, $X \setminus A$, so the block set $\{ X \setminus A : A \in \mathcal A \}$ contains $\mid \mathcal A \mid = b$ blocks.

• By definition, $r$ is the replication number of $(X, \mathcal A)$ and tells us that each point $x \in X$ is contained in $r$ many blocks. There are $b$ blocks total, so $x$ is not contained in $b - r$ blocks. So every $x \in X$ is contained in the complement of $b - r$ blocks of $\mathcal A$, i.e., every $x \in X$ is contained in $b - r$ blocks of the form $X \setminus \mathcal A$, so the replication number of $(X, \{ X \setminus A : A \in \mathcal A \})$ is $b - r$.

• We know that every block in $\mathcal A$ contains $k$ points. There are $v$ points total, so the complement of every block in $\mathcal A$ contains $v - k$ points and furthermore since we are given that $k \leq v - 2$ we have that:

(1)

\begin{align} \quad 2 \leq v - k < v \end{align}

• Lastly, let $x, y \in X$ be such that $x \neq y$ and define:

(2)

\begin{align} \quad s &= \mid \{ A \in \mathcal A : x, y \in A \} \mid \\ \quad t &= \mid \{ A \in \mathcal A : x \in A, y \not \in A \} \mid \\ \quad u &= \mid \{ A \in \mathcal A : x \not \in A, y \in A \} \mid \\ \quad v &= \mid \{ A \in \mathcal A : x, y \not \in A \} \mid \end{align}

• By definition we have that $s = \lambda$ since the every pair of distinct points $\{ x, y \}$ is contained in $\lambda$ blocks since $(X, \mathcal A)$ is a $(v, b, r, k, \lambda)$-BIBD.

• We also know that $s + t = r$ since the sets $\{ A \in \mathcal A : x, y \in A \}$ and $\{ A \in \mathcal A : x \in A, y \not \in A \}$ are disjoint and account for all sets in which the point $x$ appears in to which there are $r$ (the replication number of $(X, \mathcal A)$) by definition. Similarly, $s + u = r$.

• Lastly, note that $s + t + u + v = b$ as the sets defining $s$, $t$, $u$, and $v$ are disjoint and account for all blocks in $\mathcal A$. Hence:

(3)

\begin{align} \quad s + t + u + v &= b \\ \quad \lambda + (r - s) + (r - s) + v &= b \\ \quad v &= b - 2(r - s) - \lambda \\ \quad v &= b -2r + 2s -\lambda \\ \quad v &= b - 2r + 2\lambda - \lambda \\ \quad v &= b - 2r + \lambda \end{align}

• So the number of blocks in $\mathcal A$ not containing the pair $\{ x, y \}$ is $b - 2r + \lambda$, i.e., the number of blocks in $\{ X \setminus A : A \in \mathcal A \}$ containing the pair $\{ x, y \}$ is $b - 2r + \lambda$.

• Hence $(X, \{ X \setminus A : A \in \mathcal A \})$ is a $(v, b, b - r, v - k, b - 2r + \lambda)$-BIBD. $\blacksquare$

For example, consider $(X, \mathcal A)$ where $X = \{ 1, 2, 3, 4, 5, 6, 7 \}$ and $\mathcal A = \{ \{ 1, 2, 3 \}, \{ 3, 4, 5 \}, \{ 5, 6, 1 \}, \{ 1, 7, 4 \}, \{ 2, 7, 5 \}, \{ 3, 7, 6 \}, \{ 2, 4, 6 \} \}$. We have already seen that $(X, \mathcal A)$ is a $(7, 7, 3, 3, 1)$-BIBD. Note that $3 = k \leq v - 2 = 7 - 2 = 5$, so by Theorem 1 we can construct a new BIBD from this old one.

The complementary sets of all of the blocks in $\mathcal A$ will form our new block set $\mathcal A^*$ and contains:

(4)

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

We claim that $(X, \mathcal A^*)$ is a $(7, 7, 4, 4, 2)$-BIBD.

Clearly $\mid X \mid = 7$ and $\mid \mathcal A^* \mid = 7$.

It's not hard to verify that every point $x \in X$ is contained in exactly $4$ blocks, so the replication number of $(X, \mathcal A^*)$ is $4$.

It's very easy to see that every block contains $4$ points.

Lastly, it is not hard to check that every pair of distinct points $\{ x, y \}$ with $x \neq y$ occurs in exactly $2$ blocks, so indeed, $(X, \mathcal A^*)$ is a $(7, 7, 4, 4, 2)$-BIBD.