Skip to main content
Added a brief explanation of the doubling construction.
Source Link
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

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

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

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

Source Link
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

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