Isomorphisms/Automorphisms of Balanced Incomplete Block Designs

Isomorphisms and Automorphisms of Balanced Incomplete Block Designs

Suppose that we have two block designs $(X, \mathcal A)$ and $(Y, \mathcal B)$ with $\mid X \mid = \mid Y \mid$. We would like to establish whether these two block designs are the same in some sense - in particular, two block designs will be considered the same if the structure between the two designs is the same. This is made formal in the definitions below.

Isomorphisms of Balanced Incomplete Block Designs

Definition: If $(X, \mathcal A)$ and $(Y, \mathcal B)$ are block designs with $\mid X \mid = \mid Y \mid$ then $(X, \mathcal A)$ and $(Y, \mathcal B)$ are said to be Isomorphic if there exists a bijective function $\alpha : X \to Y$ called an Isomorphism between these block designs such that $\{ \{ \alpha (x) : x \in A \} : A \in \mathcal A \} = \mathcal B$. Furthermore, if $(X, \mathcal A)$ and $(Y, \mathcal B)$ are BIBDs then we must have that if $(X, \mathcal A)$ has $c$ repetitions of a block $A$ then $(Y, \mathcal B)$ must have $c$ repetitions of the block $\{ \alpha (x) : x \in A \}$.

For example, recall the set $X = \{ 1, 2, 3, 4, 5 \}$ and the collection $\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 \} \}$ of all $3$-element subsets of $X$. We saw that $(X, \mathcal A)$ is a $(5, 3, 3)$-BIBD.

Now consider the set $Y = \{ a, b, c, d, e \}$ and the collection $\mathcal B = \{ \{ a, b, c \}, \{ a, b, d \}, \{a, b, e \}, \{a, c, d \}, \{a, c, e \}, \{a, d, e \}, \{ b, c, d \}, \{b, c, e \}, \{ b, d, e \}, \{c, d, e \} \}$. Certain the block design $(Y, \mathcal B)$ is the same as $(X, \mathcal A)$.

To show this we define the bijection $\alpha : X \to Y$ by the rule:

(1)

\begin{align} \quad \alpha(1) &= a \\ \quad \alpha(2) &= b \\ \quad \alpha(3) &= c \\ \quad \alpha(4) &= d \\ \quad \alpha(5) &= e \end{align}

Of course determining whether two block designs are isomorphic is in general not as simple as made out to be above.

Automorphisms of Balanced Incomplete Block Designs

Definition: If $(X, \mathcal A)$ is a block design then an Automorphism on $(X, \mathcal A)$ is an isomorphism from $(X, \mathcal A)$ to itself.

For example, consider the $(5, 3, 3)$-BIBD above. Many such automorphisms exist. For example, we can define the bijection $\alpha : X \to X$ by the rule:

(2)

\begin{align} \quad \alpha (1) &= 2 \\ \quad \alpha (2) &= 3 \\ \quad \alpha (3) &= 4 \\ \quad \alpha (4) &= 5 \\ \quad \alpha (5) &= 1 \end{align}

Then the corresponding set of blocks would be:

(3)

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

Notice that this set is identical to that of $\mathcal A$. This is because the set above still denotes all of the $3$-element subsets of the $5$-element set $X = \{ 1, 2, 3, 4, 5 \}$.