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)

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 \}$.