Steiner Triple Systems

[WORK IN PROGRESS]

A Steiner Triple System – STS for short – denoted by $\left(X, {\cal T}_X\right)$ is a finite set X together with a set ${\cal T}_X$ of unordered triplets of elements of X – called triples or blocks – with an additional requirement: every (unordered) pair of elements of X must appear in exactly one of the triples:

\begin{align}
\forall a \neq b \in X, \exists! T \in {\cal T}_X, \mbox{ such that } \{a, b\} \subset T
\end{align}

The existence and uniqueness of $T \in {\cal T}_X$ allow to define the function $\tau_X$:

\begin{align}
\tau_X: \; & \left(\begin{array}{c}
X\\
2
\end{array}
\right) \to X\\
& \{a, b\} \stackrel{\text{def}}{\mapsto} c,\; \mbox{ such that } \{a, b, c\} \in {\cal T}_X \nonumber
\end{align}

End game: assuming $\left(A, {\cal T}_A\right)$ is an STS, we want to construct a larger STS $\left(X, {\cal T}_X\right)$ of which $\left(A, {\cal T}_A\right)$ would be a sub system — that is to say $X$ and ${\cal T}_X$ would be supersets respectively of $A$ and ${\cal T}_A$.

A friendly STS

The diagram below shows two representations of the STS with 7 elements (it is actually unique up to a permutation of the elements). The edges are colored by block, which is made possible by the property of being an STS.

Click on the edges to reveal the blocks. Move the nodes for clarity.

Double plus one

Double-plus-one analysis

Assume:

• An STS $\left(A, {\cal T}_A\right)$, where $\mbox{card}(A) = n$,
• An STS $\left(X, {\cal T}_X\right)$, where $\mbox{card}(X) = 2n+1$,
• $\left(A, {\cal T}_A\right)$ is a sub system of $\left(X, {\cal T}_X\right)$,

and let $B$ denote the set $X \setminus A$.

Then for each element $a \in A$ and each element $b \in B$, the unique triple in ${\cal T}_X$ including $\left\{a, b\right\}$ is a triple $\left\{a, b, b_2\right\}$, where $b_2 \in B$.

This is proven by contradiction. Indeed, assume there were a (unique) $\left\{a, b, a_2\right\} \in {\cal T}_X$, with $a_2 \in A$. Since $\left(A, {\cal T}_A\right)$ is an STS, there exists $a_3 \in A$ such that $\left\{a, a_2, a_3\right\} \in {\cal T}_A \subset {\cal T}_X$. This would contradict the uniqueness of $\left\{a, b, a_2\right\}$ $\Box$

Tau mappings

Thus it holds that:

\begin{align}
\forall a \in A, b \in B, \; \tau_X(\{a, b\}) \in B
\end{align}

For $a \in A$ and $b \in B$, let:

\begin{align}
\tau_a: \; & B \to B\\
& b \stackrel{\text{def}}{\mapsto} \tau_X(\{a, b\}) \nonumber
\end{align}

\begin{align}
\tau^b: \; & A \to B\\
& a \stackrel{\text{def}}{\mapsto} \tau_X(\{a, b\}) \nonumber
\end{align}

The following properties hold:

\begin{equation}
\tau_a \mbox{ does not have a fixed point}\label{nofixedpoint}
\end{equation}
\begin{equation}
\tau_a \mbox{ is an injective mapping}\label{injectivea}
\end{equation}
\begin{equation}
\tau_a \circ \tau_a = \mbox{id}_B\label{pair}
\end{equation}
\begin{equation}
\tau^b \mbox{ is an injective mapping}\label{injectiveb}
\end{equation}

($\ref{nofixedpoint}$), ($\ref{pair}$), ($\ref{injectivea}$), and ($\ref{injectiveb}$) derive directly from the definition of $\tau_a$ and the uniqueness of the triple that includes a given pair.

Implications of the properties of tau

($\ref{injectivea}$) implies that $\tau_a$ is a permutation of $B$, and ($\ref{nofixedpoint}$), ($\ref{pair}$) imply that all cycles are of length 2. Thus for each $a \in A$, $\tau_a$ defines a partitioning of $B$ as a set of (unordered) pairs. Let ${\cal P}_a \subset {\cal P}(B)$ denote this partitioning.

(Incidentally, this implies that $n+1 = \mbox{card}(B)$ is necessarily even.)

Because of ($\ref{injectiveb}$), $a_1 \neq a_2 \in A \implies {\cal P}_{a_1} \cap {\cal P}_{a_2} = \emptyset$. Thus $\mbox{card}\left(\bigcup_{a\in A}{\cal P}_a\right) = n\cdot{n+1\over2}$. In other words, $\bigcup_{a\in A}{\cal P}_a$ contains all possible (unordered) pairs of elements of $B$.

Or equivalently, for each $b_1 \neq b_2 \in B$, there is a unique $a \in A$ such that $\{a, b_1, b_2\} \in {\cal T}_X$. And $a = \tau_X(\{b_1, b_2\})$.

Finally, it holds that:

\begin{equation}
{\cal T}_X = {\cal T}_A \cup \bigcup_{b_1 \neq b_2 \in B}\left\{\tau_X(\{b_1, b_2\}), b_1, b_2\right\}
\end{equation}

Double-plus-one synthesis

Let us synthesize an STS of « size » $2n+1$ from an STS of « size » $n$.

Assume an STS $\left(A, {\cal T}_A\right)$, where $\mbox{card}(A) = n$ odd.

Let us enumerate $A$ as: $A = \{a_1, a_2, …, a_n\}$.

Let us consider the set $B = \{0, 1, 2, …, n\}$.

Finally let $X = A \uplus B\;$ denote the disjoint union of $A$ and $B$, and define the mapping $\tau_X: \left(\begin{array}{c}
X\\
2
\end{array}
\right) \to X$ as follows:

\begin{align}
&\mbox{for } a_i \neq a_j \in A, \; \tau_X(\{a_i, a_j\}) = \tau_A(\{a_i, a_j\})\;\in A\label{a_and_a}\\
&\mbox{for } (a_i, b) \in A \times B, \; \tau_X(\{a_i, b\}) = i \oplus b\;\in B\label{a_and_b}\\
&\mbox{for } b_1 \neq b_2 \in B, \; \tau_X(\{b_1, b_2\}) = a_{b_1 \oplus b_2}\;\in A\label{b_and_b}
\end{align}

($\oplus$ denotes the binary « xor » operator.)

Note that:

• in (\ref{a_and_b}), since $i>0,\;$ $\tau_X(\{a_i, b\})$ is different from $b$, /!\ Here there is a mistake, if $n$ is not of the form $2^k – 1$, then $i \oplus b$ could be outside $B$. A slightly different construction has to be used… stay tuned!
• in (\ref{b_and_b}), since $b_1 \neq b_2,\;$ $\tau_X(\{b_1, b_2\})$ is well defined as an element of $A$.

If we write:

\begin{align}
{\cal T}_X \;\; &\stackrel{\text{def}}{=} & \bigcup_{x \neq y \in X}\left\{\{x, y, \tau_X(\{x, y\})\}\right\}\\
& = & {\cal T}_A \uplus \biguplus_{x \neq y \in B}\left\{\{x, y, \tau_X(\{x, y\})\}\right\}\nonumber
\end{align}

then $\left(X, {\cal T}_X\right)$ is an STS.

This is proven by verifying the existence and uniqueness of a superset in ${\cal T}_X$, for each given unordered pair $\{x, y\}$.

Existence is straightforward.

For uniqueness, consider $\{x, y, z\}$ and $\{x, y, z_2\}$ in ${\cal T}_X$. Without loss of generality, we can restrict the analysis to the following three cases:

• case (\ref{a_and_a}): if $(x, y, z) = (a_i, a_j, \tau_A(\{a_i, a_j\}))$, then it is also the case that $z_2 = \tau_A(\{a_i, a_j\}) = z$.
• case (\ref{a_and_b}): if $(x, y, z) = (a_i, b, i \oplus b)$, then either:
  • subcase (\ref{a_and_b}): $z_2 = i \oplus b = z$, or
  • subcase (\ref{b_and_b}): $z_2 \in B$ and $i = b \oplus z_2$. Then $z_2 = i \oplus b = z$.
• case (\ref{b_and_b}): if $(x, y, z) = (b_1, b_2, a_{b_1 \oplus b_2})$, then $z_2 = a_i \in A$ and either:
  • subcase (\ref{a_and_b}): $b_2 = b_1 \oplus i$, hence $i = b_1 \oplus b_2$, hence $z_2 = z$, or
  • subcase (\ref{b_and_b}): $i = b_1 \oplus b_2$, hence again $z_2 = z$.

In all three cases, $z_2 = z$ $\Box$

Interpretation

In summary, we have shown how to derive an STS for a set of cardinal $2n+1$, from an STS for a set of cardinal $n$ odd.

This can be interpreted with the metaphor of a sport’s tournament.

Imagine:

• $B = \{0, 1, …, n\}$ represents a set of $n+1$ (even) players,
• $A = \{d_1, d_2, …, d_n\}$ represents a set of $n$ « days ».

The rule is that on day $d_i$, the following $n+1\over2$ matches occur: player $p$ playing with player $p \oplus i$ (for every $p$).

This results in an « optimal » organization for the tournament, in the sense that:

• on each day, every player plays exactly once,
• during the tournament, each player encounters each other player exactly once,
• at the end of the tournament (on the evening of day $d_n$) every player has played with every other player, for a total of $\left(n\cdot{ n+1\over2}\right)$ matches.

Further ideas

In general when the set $X$ is $X_n = \{1, 2, …, 2^n-1\}$, the following tau mapping produces a « natural » STS:

\begin{align}
\tau_n: \; \left(
\begin{array}{c}
X_n\\
2
\end{array}
\right)
\to X_n\\
\{i, j\} \mapsto i \oplus j\nonumber
\end{align}

With that, we obtain a sequence of STSs, each one a subsystem of the next one in the sequence:

\begin{align*}
(X_0, {\cal T}_0) \to (X_1, {\cal T}_1) \to (X_2, {\cal T}_2)\to \dots\\
\forall i \in \mathbb{N}, X_i \subset X_{i+1} \mbox{ and } {\cal T}_i \subset {\cal T}_{i+1}
\end{align*}

And $(\cup X_n, \cup {\cal T}_n)$ can be viewed as a countably infinite STS.

The figure below represents $(X_4, {\cal T}_4)$ and is identical to figure 2 (up to a permutation of the elements).