The Sum Construction of Balanced Incomplete Block Designs

The Sum Construction of Balanced Incomplete Block Designs

Suppose that we have a $(v, k, \lambda_1)$-BIBD and a $(v, k, \lambda_2)$-BIBD on the set $X$. Our goal is to take these two BIBDs and obtain a new BIBD. The following result gives us one method to construct a new BIBD called the "sum construction".

Theorem 1: If a $(v, k, \lambda_1)$-BIBD $(X, \mathcal A_1)$ and a $(v, k, \lambda_2)$-BIBD $(X, \mathcal A_2)$ exists on a set $X$ then a $(v, k, \lambda_1 + \lambda_2)$-BIBD $(X, \mathcal A)$ exists on that set.
  • Proof: Let $\mathcal A = \mathcal A_1 \cup \mathcal A_2$ be the multiset union of the multisets $\mathcal A_1$ and $\mathcal A_2$. Then $\mathcal A$ is a multiset of nonempty subsets of $X$.
  • Clearly $\mid X \mid = v$.
  • Furthermore, since every block in $\mathcal A_1$ contains $k$ points and every block in $\mathcal A_2$ contains $k$ points, we have that every block in $\mathcal A$ contains $k$ points.
  • Let $x, y \in X$ be such that $x \neq y$. Then the pair $\{x, y \}$ is contained in $\lambda_1$ blocks in $\mathcal A_1$, and the pair $\{ x, y \}$ is contained in $\lambda_2$ blocks in $\mathcal A_2$, so the pair $\{x, y \}$ is contained in $\lambda_1 + \lambda_2$ blocks in $\mathcal A$. This is true for any arbitrary pair of distinct points $x, y \in X$.
  • Hence $(X, \mathcal A)$ is a $(v, k, \lambda_1 + \lambda_2)$-BIBD. $\blacksquare$

We now prove a simple corollary to the theorem above.

Corollary 1: If a $(v, k, \lambda)$-BIBD $(X, \mathcal A)$ exists on a set $X$ then for every positive integer $s \geq 1$, a $(v, k, s\lambda)$-BIBD $(X, \mathcal A^*)$ exists on $X$.
  • Proof: Let $s \geq 1$ be any positive integer. Then set $\mathcal A^* = \underbrace{\mathcal A \cup \mathcal A \cup ... \cup \mathcal A}_{s \: \mathrm{times}}$ be the union of the multiset $\mathcal A$ with itself $s$ times. By Theorem 1, $(X, \mathcal A^*)$ is a $(v, k, \underbrace{\lambda + \lambda + ... + \lambda}_{s \: \mathrm{times}}) = (v, k, s\lambda)$-BIBD. $\blacksquare$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License