Constructing Steiner Triple Systems Algorithmically

Question

I want to create STS(n) algorithmically. I know there are STS(n)s for $n \cong 1,3 \mod 6$. But it is difficult to actually construct the triples. For STS(7) it is pretty easy and but for larger n I end up using trial and error. Is there a general algorithm that can be used?

Answer 1

The following is Bose's construction for the $6k+3$ case: Elements of the STS are labeled by ordered pairs $(x, i)$ where $x$ is in $\mathbb{Z}/(2k+1)$ and $i$ is in $\mathbb{Z}/3$. The triples are of two forms: $$\{ (x,0),\ (x,1),\ (x,2) \}\quad \mbox{for}\ x \in \mathbb{Z}/(2k+1)$$ $$\{ (x,i),\ (y,i),\ ((x+y)/2, i+1)\}\quad \mbox{for}\ x, y \in \mathbb{Z}/(2k+1),\ \mbox{with}\ x \neq y,\ i \in \mathbb{Z}/3$$

For the $6k+1$ case, one uses a messier variant due to Skolem. See Combinatorial Designs: Constructions and Analysis by Stinson for details.

Answer 2

I coded that in Sage if you want to use it immediately (see the patch, see the documentation) :

sage: from sage.combinat.designs.block_design import steiner_triple_system
sage: list(steiner_triple_system(7))
[[0, 1, 3], [0, 2, 4], [0, 5, 6], [1, 2, 6], [1, 4, 5], [2, 3, 5], [3, 4, 6]]
sage: list(steiner_triple_system(9))
[[0, 1, 5], [0, 2, 4], [0, 3, 6], [0, 7, 8], [1, 2, 3], [1, 4, 7], [1, 6, 8], [2, 5, 8], [2, 6, 7], [3, 4, 8], [3, 5, 7], [4, 5, 6]]
sage: list(steiner_triple_system(13))
[[0, 1, 6], [0, 2, 5], [0, 3, 7], [0, 4, 8], [0, 9, 11], [0, 10, 12], [1, 2, 7], [1, 3, 4], [1, 5, 9], [1, 8, 10], [1, 11, 12], [2, 3, 6], [2, 4, 12], [2, 8, 9], [2, 10, 11], [3, 5, 12], [3, 8, 11], [3, 9, 10], [4, 5, 10], [4, 6, 9], [4, 7, 11], [5, 6, 11], [5, 7, 8], [6, 7, 10], [6, 8, 12], [7, 9, 12]]

Otherwise, it turns out the proof of their existence is highly constructive -- just check the given constructions are valid -- which makes it really easy to implement (see the ebook A short course in Combinatorial Designs, by Ian Anderson and Iiro Honkala).

Nathann

Answer 3

Since this thread just got bumped to the front page, historically the very first proof (by T. P. Kirkman, On a Problem in Combinatorics, Cambridge Dublin Math. J. 2 (1847) 191-204, 1847.) of the existence of an ${\rm STS}(v)$ for all $v \equiv 1, 3 \pmod{6}$ is completely algorithmic, where you start with a singleton as the point set and an empty set as its block set (i.e., the trivial design ${\rm STS}(1)$) and successively construct an ${\rm STS}(3)$, ${\rm STS}(7)$, ${\rm STS}(9)$, and so forth by applying the same algorithms recursively to the smaller ${\rm STS}$s you have at hand. So, you conjure up ${\rm STS}$s from thin air one after another algorithmically for all admissible orders.

A modernized version of this technique is called the doubling construction. This construction can be found in a very accessible textbook "Design Theory" by C. C. Lindner and C. A. Rodger from CRC Press (in Section 1.8 of the second edition).

The doubling construction actually consists of two separate construction techniques to cover all $v \equiv 1, 3 \pmod{6}$. If you want a single algorithm to cover all orders, the same textbook also explains such a technique (originally by R. M. Wilson, Some partitions of all triples into Steiner triple systems, Lecture Notes in Math., Springer, Berlin, 411 (1974) 267-277) in Section 1.6 (in either edition).

Edit: Here's the first half of the doubling construction:

Assume that you have an ${\rm STS}(v)$ with point set $V$ and block set $\mathcal{B}$. First, you copy all points; if $a \in V$, you make a new point $a' \not\in V$ so you have another set $V'$ of the same size. You add one extra point, say $\infty$, and use $$W = \{\infty\}\cup V\cup V'$$ as the new point set. Now, for each block $\{a,b,c\} \in \mathcal{B}$, you create new blocks $\{a',b',c\}$, $\{a',b,c'\}$ and $\{a,b',c'\}$. Then you join $\mathcal{B}$ and all these pseudo-copied new blocks as well as new $v$ blocks $\{\infty, a, a'\}$, where $a \in V$. So, the new block set $\mathcal{B}'$ is $$\mathcal{B}' = \mathcal{B}\cup\{\{a',b',c\}\ \vert\ \{a,b,c\} \in \mathcal{B}\} \cup \{\{\infty, a, a'\} \ \vert \ a \in V\}.$$ You can easily check that the ordered pair $(W, \mathcal{B}')$ is an ${\rm STS}(2v+1)$.

The latter half of the construction produces an ${\rm STS}(2v+7)$ from an ${\rm STS}(v)$ in a little more complicated way. Applying these two algorithms recursively gives you an ${\rm STS}(v)$ for all $v \equiv 1, 3 \pmod{6}$, covering all $v$ satisfying the necessary conditions for the existence of an ${\rm STS}(v)$.

Answer 4

One standard algorithm for constructing Steiner triple systems is the "hill climbing" procedure. You will find it described in "Combinatorial algorithms: generation, enumeration, and search" by Kreher and Stinson, and in many papers. This procedure allows you to construct large families of triple systems on the same number of points, in comparison to the standard recursive constructions which give just one on each size.