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:
- Lastly, let $x, y \in X$ be such that $x \neq y$ and define:
- 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:
- 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)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.