Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
In general, books that deal with the subject are replete with methods of construction. The proof of existence is in fact constructive. –  Mariano Suárez-Alvarez Aug 4 '11 at 15:52
add comment

4 Answers

up vote 7 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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)$.

share|improve this answer
    
Your nice answer makes me glad I bumped it (I fixed a broken link). –  Peter Shor Aug 18 '13 at 12:53
    
@Peter Thank you for your kind comment! –  Yuichiro Fujiwara Aug 19 '13 at 17:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.