Construction techniques for Steiner triple systems
Jeff Dinitz
University of Vermont
USA
We will demonstrate many techniques for making designs by concentrating on the construction of Steiner triple systems.
A Steiner triple system on v points (denoted STS(v))
is a (v, 3,1) –design.
So it has v points, blocks of size 3, and each pair of points in exactly one block.
Example 1: An STS(7), the fano plane.
V = {1,2,3,4,5,6,7}
B = {156, 137, 124, 267, 235, 346, 457}
(to save space we write abc rather than {a,b,c}
This BIBD has a nice diagram
Example 2: An STS(9)
V = {1,2,3,4,5,6,7,8,9}
B = {123, 456, 789 147,258, 369, 159, 267, 348, 168, 249, 357}
Remember the nice geometric representation:
Some early history:
I n 1844, STS were first defined by W.S. Woolhouse, he asked:
For what positive integers v does there exist a Steiner triple system of order v.
In 1847, the existence problem was solved by Rev. T.P. Kirkman.
In 1853, Steiner asked in a more geometrical way: For what positive integers v does there exist a Steiner triple system of order v.
In 1859, Steiner's problem was solved (again) by Reiss.
In 1893, proved again by E.H. Moore (gave some very interesting constructions).
Necessary conditions:
Theorem: An STS(v) can only exist if v º 1 or 3 (mod 6).
Proof: Looking at the number r of blocks on a point we see that
v = 2 r + 1, hence v must be odd.
Now, the number of blocks b = 1/6 v(v – 1). So 6 divides v(v – 1).
So we must have that v º 1 or 3 (mod 6). J
v=
1.
3.
7. Yes – the fano plane
9. Yes – the affine plane of order 3
13. ??
15. ??
We first give three recursive constructions, then two direct constructions, then one final recursive construction.
Existence for v < 100
1
3
7
9
13
15
19
21
25
27
31
33
37
39
43
45
49
51
55
57
61
63
67
69
73
75
79
81
85
87
91
93
97
The Bose construction
For every v º 3 (mod 6), there exists an STS(v).
Let v = 3s for some odd s. Let L be an idempotent symmetric latin square of side s.
L =
s s s
Example: We make an STS(15)
The semi-direct product construction
(E.H. Moore 1903)
If there exists a STS(u) and an STS(v) which contains a sub STS(w),
then there exists a STS(u (v - w) + w).
A subdesign of a design is a subset of the points together with the blocks containing only those points that is itself a block design.
Note. Every design has a subdesign of size 1 and every STS has a sub STS of order 3.
Homework: show that if there is a STS(v) which contains a sub STS(w), then v ³ 2 w + 1.
That this is also a necessary condition was proven by Doyen and
Wilson in 1971.
The construction: We need a latin square L of order v - w.
L =
Example: construct a STS(31),
31= 7(7 - 3) + 3
The 2v + 1 construction
Theorem. If there exists an STS(v), then there exists an STS(2v + 1).
Furthermore, the resulting design has a subdesign of order v.
The construction:
Let X = {x1, x2, … , xv} be the points of an STS(v).
Now take a round robin league schedule for v + 1 teams labeled
1, 2, … , v + 1. For each i =1, 2, … , v adjoin xi to each pair occurring on day i of the schedule. Finally add all the triples in an STS(v) on the points x1, x2, … , xv. The result is an STS(2v + 1) containing an
STS(v).
Example: v = 7.
Week games
1 1,8 2,7 3,6 4,5
2 2,8 3,1 4,7 5,6
3 3,8 4,2 5,1 6,7
4 4,8 5,3 6,2 7,1
5 5,8 6,4 7,3 1,2
6 6,8 7,5 1,4 2,3
7 7,8 1,6 2,5 3,4
Finally adjoin an STS(7) on the points {x1, x2, … , x7}.
{x1, x2, x4}, {x2, x3, x5}, {x3, x4, x6}, {x4, x5, x7}, {x5, x6, x1}, {x6, x7, x2}, and {x7, x1, x3}.
The result is an STS(15)
We will show in the next lecture that there always exists the necessary round robin league schedule. It's just another idempotent symmetric latin square.
Binary triple systems:
(a direct construction)
Let V be the set of all non-zero binary vectors of length n.
Say that {u, v, w} is a triple in the design if u + v + w = 0.
Number of points =
Check that two points are in exactly one triple.
Example n = 3. (The STS(7))
Difference Families
The idea is to find a set of "base blocks" that when developed in a group give all the blocks of the block design.
Examples.
1) Consider the differences in set {0, 1, 3} in Z7, the cyclic group of order 7.
2) Consider {0,1,4} and {0,2,8} in Z13.
Definition: Let G be an additive abelian group of order v. Then t k-element subsets of G, Bi = { bi,1, bi,2 , …, bi,k} (1 £ i £ t) form a
(v, k, l) - difference family if every nonzero element of G occurs l times among the differences bi,x - bi,y (i = 1, … , t ; x,y = 1,… ,k). The sets Bi are called the base blocks.
If B1, … , Bt form a (v,k,l) difference family, then the translates of the base blocks, namely Bi+g = {bi,1+g, bi,2+g , … , bi,k+g}
(i = 1, …, t, g Î G ), form a (v,k,l) - BIBD.
The BIBD is cyclic if G = Zv and in this case the difference family is a cyclic difference family.
Example: Base blocks for a cyclic (19,4,2) – design
{0, 1, 3, 12} {0, 1, 5, 13} {0, 4, 6, 9}
For a Steiner triple system of order v, note that the number of blocks is b = 1/6 (v (v - 1)). In a cyclic STS, each base block will generate v blocks, thus these can only exist if v - 1 is divisible by 6.
So this only works for the v º 1 (mod 6) case.
Note that the number of base blocks will be (v 1) / 6
A direct construction of cyclic STS
This construction is in the finite field GF(q) where q = 6 t + 1 is a prime power congruent to 1 modulo 6.
Let be a primitive root of unity (a generator of the multiplicative group of the field). Then
{{i + j , 2t+ i + j , 4t+i + j} : 0 i t , j GF(q) }
is the set of blocks of an STS(q) where the symbols are
the elements of GF(q).
(proof – homework)
Example: q = 19 = 6 3 + 1
In GF(19), 2 is a primitive root of unity and the powers of 2 are
n / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15 / 16 / 172n / 1 / 2 / 4 / 8 / 16 / 13 / 7 / 14 / 9 / 18 / 17 / 15 / 11 / 3 / 6 / 12 / 5 / 10
We get 3 base blocks
i = 0 i = 1 i = 2
j = 0 {20,26,212} {21,27,213} {22,28,214}
{1,7,11} {2,14,3} {4,9,6}
j = 1 {2,8,12} {3,15,4} {5,10,7}
j =2 {3,9,13} {4,16,5} {6,11,8}
… … … …
j=18 {0,6,10} {1,13,2} {3,8,5}
These 19 3 = 57 blocks form an STS(19).
Short orbits
When v 3 (mod 6) we can still make cyclic STS.
We just need to have one base block that has a short orbit.
Look at the following base blocks when v = 15.
{0, 1, 4} {0, 2, 9} {0, 5, 10}
{0,5,10} is called the short block (generates the short orbit).
(v,3,1) cyclic difference families for 7 £v £49
Short blocks shown in italics.
7 – 0 1 3
13 – 0 1 4 , 0 2 7
15 – 0 1 4 , 0 2 9 , 0 5 10
19 – 0 1 4, 0 2 9 , 0 5 11
21 – 0 1 3 , 0 4 12 , 0 5 11 , 0 7 14
25 – 0 1 3 , 0 4 11 , 0 5 13 , 0 6 15 ,
27 – 0 1 3 , 0 4 11 , 0 5 15 , 0 6 14 , 0 9 18
31 – 0 1 12 , 0 2 24 , 0 3 8 , 0 4 17 , 0 6 16
33 – 0 1 3 , 0 4 10 , 0 5 18 , 0 7 19 , 0 8 17 , 0 11 22
37 – 0 1 3 , 0 4 26 , 0 5 14 , 0 6 25 , 0 7 17 , 0 8 21
39 – 0 1 3 , 0 4 18 , 0 5 27 , 0 6 16 , 0 7 15 , 0 9 20 , 0 13 26
43 – 0 1 3 , 0 4 9 , 0 6 28 , 0 7 23 , 0 8 33 , 0 11 30 , 0 12 26
45 – 0 1 3 , 0 4 10 , 0 5 28 , 0 7 34 , 0 8 32 , 0 9 29 , 0 12 26 , 0 15 30
49 – 0 1 3 , 0 4 9 , 0 6 17 , 0 7 23 , 0 8 30 , 0 10 31 , 0 12 36 , 0 14 34
It is known that cyclic Steiner triple systems exist
for all orders v º 1 or 3 (mod 6).
In two recent papers (D. and Rodney 1997) and (D. and Shalaby 2002), it was shown that for every v º 1 or 3 (mod 6) there exist a set of disjoint triples which are the base blocks for a cyclic STS(v).
Novak's conjecture: Given any cyclic Steiner triple system, there exist a set of disjoint blocks which generate the STS. (try it)
The Wilson Fundamental Construction
This is the most powerful recursive construction and is very general.
We will use this to show that STS exist for all v º 1 (mod 6).
Our application:
Theorem: If there exists two MOLS of order 3t, an STS(6t+1) and an
STS(6s+1) (0 £ s £ t), then there exists an STS(18t +6s +1).
Example: Let t = 3 and s = 1 to construct an STS(61).
Two new ingredients are needed:
A 3-GDD(23) A 3-GDD(24)
These are called group divisible designs.
We now use the "master" transversal design from the two MOLS(9). First, delete 6 points from the bottom group and give each resulting point weight 2. Also add a new point ¥. Note that we now have
9 ´ 2 ´ 3 + 3 ´ 2 + 1 = 61 points.
Replace each block of the transversal design with whichever of the two GDD's above is the right length (3 or 4). Put an STS(19) on each of the first three groups (plus the point ¥) and put an STS(7) on the points of the last group (plus the point ¥) . The result is an STS(61). J
Lets see what we can make with this theorem.
Remember we only need 2 MOLS(3t), STS(6t + 1), STS(6s +1) and
0 £ s £ t. And we get an STS(6(3t + s) +1)
t / s / v1 / 0,1 / 19,25
3 / 0,1,2,3 / 55,61,67,73
4 / 0,1,2,3,4 / 73,79,85,91,97
5 / 0, 1, …, 5 / 91,97,103,109,115,121
6 / 0, 1, …, 6 / 109, …, 145
7 / 0, 1, … , 7 / 127, … , 169
Obviously, we get an overlap in coverage.
As a corollary to the construction, we get the following theorem:
Theorem: If t ¹ 2 and if there exists STS(6s + 1) for all (0 £ s £ t),
then there exists an STS(v) for every 18 t +1 £ v £ 24 t +1 with
v º 1 (mod 6).
This gives us an STS(v) for all admissible v.
Since 24 t + 1 ³ 18 (t + 1) + 1 ( if t ³ 3)
so our values overlap once t ³ 3.
Stinson's hill-climbing algorithm
A very fast and effective algorithm for getting "random" triple systems
(even if l 1).
The idea: Want to construct b = v(v 1)/6 blocks that constitute the STS.
Add one block at a time until there is a problem. Then subtract one existing block and switch in one new block.
The algorithm:
blocksRemaining := v(v-1)/6
D := Ø
while blocksRemaining > 0 do
begin
Pick a random element x appearing < (v - 1)/2 times in D ;
Pick random pairs {x, y} , {x, z} not covered by blocks in D ;
if pair {y, z} appears in D
then begin
D := D - block containing pair {y, z} ;
blocksRemaining := blocksRemaining + 1
end;
D := D È block {x, y, z} ;
blocksRemaining := blocksRemaining - 1
end
Enumeration
Two designs D1 and D2 are isomorphic if there is a bijection between the points of the designs that maps the blocks of D1 to the blocks of D2
In general, for a given parameter set (v, k, l) there are many nonisomorphic (v, k, l) - designs.
For STS this again provides a good example of the combinatorial explosion
v / # of nonisomorphic STS(v) / Notes3 / 1
7 / 1
9 / 1
13 / 2
15 / 80 / Cole, Cummings, 1912
19 / 11,084,874,829 / Kaski and Östergård, 2001
21 / ??
Let NN(n) denote the number of nonisomorphic STS(n).
In 1974, Wilson proved an asymptotic bound on NN(n) that depended on the truth of the van der Waerden Permanent Conjecture.
In 1982, this conjecture was proven true so we have Wilson’s bound.
Theorem: limn NN(n) =