18.1: Steiner and Kirkman Triple Systems

In \(1844\), W.S.B. Woolhouse, editor of the Ladies and Gentleman’s Diary, posed that publication’s annual prize problem:

Determine the number of combinations that can be made of \(n\) symbols, \(p\) symbols in each, with this limitation, that no combination of \(q\) symbols which may appear in any one of them shall be repeated in any other.

If we take \(q = 2\) then this is essentially a design with \(k = p\) and \(v = n\), although it need not be balanced; some pairs might appear once while other pairs do not appear. Although some responses were printed in \(1845\), they were not satisfactory, and in \(1846\) by Woolhouse repeated the question for the special case \(q = 2\) and \(p = 3\).

In \(1847\), Rev. Thomas Kirkman (previously mentioned in Chapter \(13\)) found a complete solution to this problem in the case where the design is balanced (with \(λ = 1\)), and made some progress towards solving the complete problem. In our terminology, his solution completely determined the values of \(v\) for which a BIBD\((v, 3, 1)\) exists.

Although Steiner did not study triple systems in \(1853\), he came up with Kirkman’s result independently, and his work was more broadly disseminated in mathematical circles, so these structures still carry his name. Despite this, as we shall see in the next section, there is a related problem that has been named after Kirkman.

Definition: Triple System

A triple system is a (regular) balanced design in which every block has cardinality \(3\); that is, a BIBD\((v, 3, λ)\).

A Steiner triple system is a triple system with \(λ = 1\).

Example \(\PageIndex{1}\)

The cyclic BIBD\((19, 3, 1)\) given in Example 17.2.2 is a Steiner triple system. So is the design on \(7\) points given by

\[\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \{2, 4, 6\}, \{2, 5, 7\}, \{3, 4, 7\}, \{3, 5, 6\}\]

Notation

Since the only variable in a Steiner triple system is \(v\), for such a system on v points we use the notation STS\((v)\).

Triple systems might seem like a very special case of designs, and it would be reasonable to wonder why we have chosen to single these out for special study and attention. The answer is that triple systems can be thought of as the smallest interesting examples of designs, since (as noted previously) if \(k = 1\) there are no pairs in any block and the design is trivial; and if \(k = 2\) then the blocks are simply copies of every possible pair from the set \(V\). So triple systems are a natural starting point when we are learning about designs: they include examples that are not too big or complicated to understand, but are non-trivial.

If you are now convinced that triple systems are worth studying, you might still be wondering about Steiner triple systems in particular. We’ve seen that the method of repeating blocks allows us to construct a triple system for any \(λ\) if we first have a triple system with \(λ = 1\), so Steiner triple systems will be the rarest kind of triple system, and are therefore of particular interest.

In the remainder of this section, we will prove Kirkman’s result characterising the values of \(v\) for which an STS\((v)\) exists. To do this, we will require two results about the existence of special kinds of Latin squares. There are many connections in combinatorics!

The special kinds of Latin squares we require will be symmetric: that is, the entry in row \(i\) and column \(j\) must equal the entry in row \(j\), column \(i\). We will also specify the entries on the main diagonal: the positions for which the row number and the column number are the same.

Lemma \(\PageIndex{1}\)

For every odd \(n\), there is a symmetric Latin square of order \(n\) with \(1, 2, . . . , n\) appearing in that order down the main diagonal.

Proof

Make the entries of the first row

\[1,\dfrac{(n + 3)}{2}, 2,\dfrac{(n + 5)}{2}, 3, . . . ,\dfrac{(n − 1)}{2}, n,\dfrac{(n + 1)}{2}.\]

For \(i ≥ 2\), the entries of row \(i\) will be the entries of row \(i − 1\) shifted one position to the left.

Clearly all of the entries in any row are distinct. Also, since it takes \(n\) shifts to the left to return to the starting point, all of the entries in any column must be distinct.

Since the entry in row \(a\), column \(b\) moves to the entry in row \(a + 1\) column \(b − 1 (\text{mod } n)\), the positions in which this entry appears will be precisely the positions \((x, y)\) for which \(x+y ≡ a + b (\text{mod } n)\). Since \(i + j = j + i\), the entry in column \(i\) of row \(j\) will be the same as the entry in column \(j\) of row \(i\). Thus, the Latin square is symmetric.

The same argument shows that the entry in row \(i\) and column \(i\) will be the entry in position \(2i − 1 (\text{mod } n)\) of row \(1\). But this is precisely where \(i\) has been placed, so this entry will be \(i\), as desired.

Example \(\PageIndex{2}\)

When \(n = 11\), here is the (symmetric) Latin square constructed in the proof of Lemma 18.1.1:

\[ 1\; \; 7\; \; 2\; \; 8\; \; 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \\ 7\; \; 2\; \; 8\; \; 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \\ 2\; \; 8\; \; 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \\ 8\; \; 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \\ 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \\ 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \\ 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9\\ 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9 \;\;4 \\ 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9 \;\;4 \;\;10 \\ 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9 \;\;4 \;\;10 \;\; 5 \\ 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9 \;\;4 \;\;10 \;\; 5 \;\; 11 \]

You can see that this construction will not work when \(n\) is even, since the values of some of the entries given in the formulas would not be integers. In fact, it is not possible to construct a symmetric Latin square of order \(n\) with the entries \(1, . . . n\) down the main diagonal when \(n\) is even. Fortunately, it is possible to construct something similar that will achieve what we will require.

Lemma \(\PageIndex{2}\)

For every even \(n\), there is a symmetric Latin square of order \(n\) with the values \(1, . . . , \dfrac{n}{2}, 1, . . . , \dfrac{n}{2}\) appearing in that order down the main diagonal.

Proof

Make the entries of the first row.

\[ 1,\dfrac{(n + 2)}{2}, 2,\dfrac{(n + 4)}{2}, 3, . . . ,\dfrac{(n − 2)}{2}, n. \]

For \(i ≥ 2\), the entries of row \(i\) will be the entries of row \(i − 1\) shifted one position to the left.

The same arguments as in the proof of Lemma 18.1.1 show that this is a symmetric Latin square. The entry in row \(i\) and column \(i\) will be the entry in position \(2i − 1 (\text{mod } n)\) of row \(1\). These are the entries \(1, 2, . . . , \dfrac{n}{2}\) and since position

\[ \dfrac{2(n + 2j)}{2} − 1 ≡ 2j − 1 (\text{mod } n) \]

the entries in positions \((j, j)\) and \((\dfrac{(n + 2j)}{2},\dfrac{(n + 2j)}{2})\) will be the same, so each of these entries will be repeated in the same order.

Example \(\PageIndex{3}\)

When \(n = 10\), here is the (symmetric) Latin square constructed in the proof of Lemma 18.1.2:

\[1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10\\ 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10 \;\;1\\ 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10\;\;1\; \; 6 \\ 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\\ 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\\ 8\; \; 4\; \; 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\\ 4\; \; 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\\ 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\\ 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\\ 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\]

We are now ready to characterise the values of \(v\) for which there is an STS\((v)\).

Theorem \(\PageIndex{1}\)

An STS\((v)\) exists if and only if \(v ≡ 1, 3 (\text{mod } 6)\).

Proof

We prove the two implications separately.

\((⇒)\) Suppose that an STS\((v)\) exists. Then by Theorem 17.1.3, the values

\[λ\dfrac{v-1}{k-1} = \dfrac{v-1}{2} \text{ and } λ\dfrac{v(v-1)}{k(k-1)} = \dfrac{v(v-1)}{6} \]

must be integers. The first of these conditions tells us that \(v\) must be odd, so must be \(1\), \(3\), or \(5 (\text{mod } 6)\). If \(v ≡ 5 (\text{mod } 6)\), then \(v = 6q + 5\) for some \(q\), so

\[\dfrac{v(v − 1)}{6} = \dfrac{(6q + 5)(6q + 4)}{6}.]

Since neither \(6q + 5\) nor \(6q + 4\) is a multiple of \(3\), this will not be an integer. Thus, the second condition eliminates the possibility \(v ≡ 5 (\text{mod } 6)\). Therefore, \(v ≡ 1, 3 (\text{mod } 6)\).

\((⇐)\) Suppose that \(v ≡ 1, 3 (\text{mod } 6)\). We give separate constructions of Steiner triple systems on \(v\) points, depending on the congruence class of \(v\). We will use the graph theoretic approach to the problem, so our goal is to find colour classes for the edges of \(K_v\) such that each colour class consists of a \(K_3\).

\(v ≡ 3 (\text{mod } 6)\) Say \(v = 6q + 3\). Label the vertices of \(K_{6q+3}\) with

\[u_1, . . . , u_{2q+1}; v_1, . . . , v_{2q+1}; and w_1, . . . , w_{2q+1}.\]

By Lemma 18.1.1, there is a Latin square of order \(2q + 1\) in which for every \(1 ≤ i ≤ 2q + 1\), the entry \(i\) appears in position \((i, i)\).

For \(1 ≤ i\), \(j ≤ 2q + 1\) with \(i \neq j\), if the entry in position \((i, j)\) of this Latin square is \(\ell\), then use new colours to colour the edges that join the vertices in each of the following sets:

\[\{u_i , u_j , v_{\ell} \}; \{v_i , v_j , w_{\ell} \}; \text{ and } \{w_i , w_j , u_{\ell}\}.\]

Since the Latin square was symmetric, both position \((i, j)\) and position \((j, i)\) give rise to the same colour classes. Since we consider every pair \(i \neq j\), every edge of the form \(u_iu_j\), \(v_iv_j\), or \(w_iw_j\) has been coloured (we must have \(i \neq j\) for such an edge to exist). Since the square is Latin, every possible entry \(\ell\) occurs somewhere in row \(i\), so every edge of the form \(u_iv_{\ell}\), \(v_iw_{\ell}\), or \(w_iu_{\ell}\) has been coloured, except that we did not look at the entry of the Latin square in the position \((i, j)\), where \(i = j\). We know that the entry in position \((i, i)\) is \(i\), so the edges of the form \(u_iv_i\), \(v_iw_i\), and \(w_iu_i\) are the only edges that have not yet been coloured.

For each \(1 ≤ i ≤ 2q + 1\), make the edges joining \(u_i\), \(v_i\), and \(w_i\) into one colour class.

Now all of the edges of \(K_{6q+3}\) have been coloured, and each colour class forms a \(K_3\), so we have constructed a Steiner triple system.

\(v ≡ 1 (\text{mod } 6)\). Say \(v = 6q + 1\). Label the vertices of \(K_{6q+1}\) with

\[u_1, . . . , u_{2q}; v_1, . . . , v_{2q}; and w_1, . . . , w_{2q}; x.\]

By Lemma 18.1.2, there is a Latin square of order \(2q\) in which for every \(1 ≤ i ≤ q\), the entry \(i\) appears in position \((i, i)\), and for every \(q + 1 ≤ i ≤ 2q\), \(i − q\) appears in position \((i, i)\).

For \(1 ≤ i\), \(j ≤ 2q\) with \(i \neq j\), if the entry in position \((i, j)\) of this Latin square is \(\ell\), then use new colours to colour the edges that join the vertices in each of the following sets:

\[\{u_i , u_j , v_{\ell} \}; \{v_i , v_j , w_{\ell} \}; \text{ and } \{w_i , w_j , u_{\ell}\}.\]

Since the Latin square was symmetric, both position \((i, j)\) and position \((j, i)\) give rise to the same colour classes. Since we consider every pair \(i \neq j\), every edge of the form \(u_iu_j\), \(v_iv_j\), or \(w_iw_j\) has been coloured (we must have \(i \neq j\) for such an edge to exist). Since the square is Latin, every possible entry \(\ell\) occurs somewhere in row \(i\), so every edge of the form \(u_iv_{\ell}\), \(v_iw_{\ell}\), or \(w_iu_{\ell}\) has been coloured, except that we did not look at the entry of the Latin square in the position \((i, j)\), where \(i = j\). We know that the entry in position \((i, i)\) is \(i\) (if \(i ≤ q\)) or \(i − q\) (if \(i > q\)), so the only edges that have not yet been coloured are the edges of the form \(u_iv_i\), \(v_iw_i\), and \(w_iu_i\) when \(i ≤ q\) and \(u_iv_{i−q}\), \(v_iw_{i−q}\), and \(w_iu_{i−q}\) when \(i > q\), as well as every edge incident with \(x\).

For each \(1 ≤ i ≤ q\), make the edges joining \(u_i\), \(v_i\), and \(w_i\) into one colour class. Observe that amongst the remaining edges that are not incident with \(x\), every vertex other than \(x\) is an endvertex of precisely one of the edges. For example, if \(i ≥ q\) then \(u_iv_{i−q}\) is one of these edges, while if \(i < q\), \(w_{i+q}u_i\) is one of these edges, so either way, \(u_i\) is an endvertex of precisely one of these edges. Therefore, if for every \(q + 1 ≤ i ≤ 2q\) we use new colours to colour the edges that join the vertices in each of the following sets:

\[{u_i , v_{i−q}, x}; {v_i , w_{i−q}, x}; and {w_i , u_{i−q}, x},\]

every edge incident with \(x\) (as well as all of our other remaining edges) will have been coloured.

Now all of the edges of \(K_{6q+1}\) have been coloured, and each colour class forms a \(K_3\), so we have constructed a Steiner triple system.

Example \(\PageIndex{4}\)

We will use the method of Theorem 18.1.1 to construct an STS(\(15\)).

We have \(15 = 6(2) + 3\), so \(q = 2\). The points of our design will be \(u_i\), \(v_i\), and \(w_i\) for \(1 ≤ i ≤ 2q + 1 = 5\), and we will require a symmetric Latin square of order \(5\). Here is the square:

\[1\; \; 4\; \; 2\; \; 5\; \; 3\\ 4\; \; 2\; \; 5\; \; 3\; \; 1\\ 2\; \; 5\; \; 3\; \; 1\; \; 4 \\ 5\; \; 3\; \; 1\; \; 4\; \; 2\\ 3\; \; 1\; \; 4\; \; 2\; \; 5\]

Here are the blocks we form from this Latin square:

\[ \{u_1, u_2, v_4\}, \{v_1, v_2, w_4\}, \{w_1, w_2, u_4\},\;\;\;\;\;\; \{u_1, u_3, v_2\}, \{v_1, v_3, w_2\}, \{w_1, w_3, u_2\}, \\ \{u_1, u_4, v_5\}, \{v_1, v_4, w_5\}, \{w_1, w_4, u_5\},\;\;\;\;\;\; \{u_1, u_5, v_3\}, \{v_1, v_5, w_3\}, \{w_1, w_5, u_3\}, \\ \{u_2, u_3, v_5\}, \{v_2, v_3, w_5\}, \{w_2, w_3, u_5\},\;\;\;\;\;\; \{u_2, u_4, v_3\}, \{v_2, v_4, w_3\}, \{w_2, w_4, u_3\}, \\ \{u_2, u_5, v_1\}, \{v_2, v_5, w_1\}, \{w_2, w_5, u_1\},\;\;\;\;\;\; \{u_3, u_4, v_1\}, \{v_3, v_4, w_1\}, \{w_3, w_4, u_1\}, \\ \{u_3, u_5, v_4\}, \{v_3, v_5, w_4\}, \{w_3, w_5, u_4\},\;\;\;\;\;\; \{u_4, u_5, v_2\}, \{v_4, v_5, w_2\}, \{w_4, w_5, u_2\}, \\ \{u_1, v_1, w_1\}, \{u_2, v_2, w_2\}, \{u_3, v_3, w_3\}, \{u_4, v_4, w_4\}, \{u_5, v_5, w_5\} \]

After solving Woolhouse’s problem, Kirkman noticed that his construction of an STS(\(15\)) had a very nice property. He challenged others to come up with this solution in the following problem that he published in the \(1850\) edition of the Ladies and Gentleman’s Diary:

Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.

This has become known as Kirkman’s Schoolgirl Problem.

Although this problem begins by requiring an STS(\(15\)), it has the additional requirement that it must be possible to partition the blocks of this design (the rows of young ladies) into seven groups (of five blocks each) so that every point (young lady) appears exactly once in each group. This extra requirement comes from the fact that each of the young ladies must walk out every day, and can only be in one row in any given day.

Definition: Resolvable Design

A BIBD is a resolvable design if the blocks of the design can be partitioned into sets, each of which forms a partition of the point set of the BIBD. A Kirkman triple system is a resolvable Steiner triple system.

Notice that since each block has \(3\) points in it, a Kirkman triple system is only possible if \(\dfrac{v}{3}\) is an integer. Since a Kirkman triple system is also a Steiner triple system, this means that we must have \(v ≡ 3 (\text{mod } 6)\).

There are seven non-isomorphic Kirkman triple systems of order \(15\).

Kirkman triple systems are also known to exist whenever \(v ≡ 3 (\text{mod } 6)\).

Theorem \(\PageIndex{2}\) (Chaudhury-Wilson, 1971)

There is a Kirkman triple system whenever \(v ≡ 3 (\text{mod } 6)\).

Exercise \(\PageIndex{1}\)

1) For \(v = 37\), give the Latin square you would have to use in order to construct a Steiner triple system using the method described in the proof of Theorem 18.1.1.

2) For \(v = 39\), give the Latin square you would have to use in order to construct a Steiner triple system using the method described in the proof of Theorem 18.1.1.

3) For \(v = 19\), use the method described in the proof of Theorem 18.1.1 to construct a Steiner triple system.

4) Is the STS(\(15\)) constructed in Example 18.1.4 a Kirkman triple system? Explain your answer.

[Hint: Think of Pigeonhole-type arguments.]

5) Find all values of \(λ\) for which a triple system on six varieties exists. For each such value of \(λ\), either give a design or explain how to construct it.

[Hint: Begin by showing that if such a design exists, its parameters are \((2r, 6, r, 3, \dfrac{2r}{5})\). Then determine what values \(r\) can take on. Finally use some results about how to construct designs.]

6) Construct an STS(\(13\)) design. Show your work.

7) Let \(v = 21\).

(a) Write down the Latin square that you would use to construct a Steiner triple system (for this value of \(v\)) using the method described in the proof of Theorem 18.1.1.

(b) For the resulting Steiner triple system, which triples contain:

(i) both \(u_1\) and \(u_3\)?

(ii) both \(v_2\) and \(w_7\)?

(iii) both \(u_3\) and \(w_4\)?

(iv) both \(v_5\) and \(w_5\)?

(v) \(w_3\)?

8) Let \(v = 27\).

(a) Write down the Latin square that you would use to construct a Steiner triple system (for this value of \(v\)) using the method described in the proof of Theorem 18.1.1.

(b) For the resulting Steiner triple system, which triples contain:

(i) both \(v_3\) and \(u_8\)?

(ii) both \(u_4\) and \(w_4\)?

(iii) both \(u_5\) and \(w_4\)?

(iv) \(v_2\)?

(v) both \(v_2\) and \(v_5\)?