Page 59 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 59
iusz Meszka: Combinatorial Designs 47
Heffter’s difference problem.
The number of pairwise nonisomorphic Steiner triple systems increases rapidly with
v . While STS(7) and STS(9) are unique (up to isomorphism), there are two STS(13)’s, 80
STS(15)’s and 11, 084, 874, 829 STS(19)’s.
The existence of Steiner triple systems for each admissible order v ≡ 1, 3 (mod 6) may
be also proven by applying two recursive constructions.
v → 2v + 1 construction.
Let (V, ) be an STS(v ) and let (X , ) be a one-factorization of the complete graph of
order v + 1 on the set of vertices X . Let = {{vi , x , y } : vi ∈ V, {x , y } ∈ Fi ∈ }. Then
(V ∪ X , ∪ ) is an STS(2v + 1) with a subsystem STS(v ).
The second construction uses the existence of one-factorizations in some circulant
graphs, determined by Stern-Lenz Lemma.
Lemma 14. A circulant graph C (n ; d 1, d 2, . . . , d s ) has a 1-factorization if and only if
n / gcd(d i , n ) is even for at least one generator d i .
v → 2v + 7 construction.
Let (V, ) be an STS(v ). Let (X , ) be a collection of edge-disjoint one-factors in the
complete graph Kv +7 on the set X , and moreover let T be a set of v + 7 triples, which to-
gether with one-factors in form a partition of the edge set of Kv +7. Let = {{vi , x , y } :
vi ∈ V, {x , y } ∈ Fi ∈ }. Then (V ∪X , ∪ ∪T ) is an STS(2v +7) with a subsystem STS(v ).
Another well studied class of Steiner triple systems are projective triple systems. Let
Wm be an (m + 1)-dimensional vector space over F2. Let ⊕ be the operation of vector
addition in Wm . Any two nonzero (m + 1)-vectors x and y determine uniquely a third
vector x ⊕ y in Wm , where addition is performed modulo 2 componentwise. Let every
nonzero vector in Wm+1 be represented by a point in a set V of cardinality 2m+1 − 1.
Every two distinct points, corresponding to x and y, define a unique triple formed by
{x, y, x⊕y}. The STS(2m+1 −1) produced in this way is called a projective triple system and
it is often denoted by PG(m , 2) (just consider the triples as lines in the projective space
over GF(2)). To simplify notation, let every point in V be labeled by an integer whose
binary representation is determined by the coordinates of its corresponding vector. Thus
V (PG(m , 2)) = {1, 2, . . . , 2m+1 − 1}.
A partial triple system PTS(v ) is a pair (V, ), where |V | = v and is a collection of
3-element subsets of V such that each unordered pair of elements of V occurs in at most
one triple of . Let (V, ) be a PTS(v ) and (W, ) be an STS(w ) for which V ⊆ W and
⊆ . Then (W, ) is an embedding of (V, ).
Theorem 15. Any partial triple system PTS(v ) can be embedded in an STS(w ) if w = 1, 3
(mod 6) and w ≥ 2v + 1.
Theorem 16. Let v, w ≡ 1, 3 (mod 6) and v ≥ 2w + 1. Then there exists an STS(v ) contain-
ing an STS(w ) as a subsystem.
Exercise 14.
Apply Skolem construction to get an STS(13).
Exercise 15.
Show that a cyclic STS(9) does not exist.
Heffter’s difference problem.
The number of pairwise nonisomorphic Steiner triple systems increases rapidly with
v . While STS(7) and STS(9) are unique (up to isomorphism), there are two STS(13)’s, 80
STS(15)’s and 11, 084, 874, 829 STS(19)’s.
The existence of Steiner triple systems for each admissible order v ≡ 1, 3 (mod 6) may
be also proven by applying two recursive constructions.
v → 2v + 1 construction.
Let (V, ) be an STS(v ) and let (X , ) be a one-factorization of the complete graph of
order v + 1 on the set of vertices X . Let = {{vi , x , y } : vi ∈ V, {x , y } ∈ Fi ∈ }. Then
(V ∪ X , ∪ ) is an STS(2v + 1) with a subsystem STS(v ).
The second construction uses the existence of one-factorizations in some circulant
graphs, determined by Stern-Lenz Lemma.
Lemma 14. A circulant graph C (n ; d 1, d 2, . . . , d s ) has a 1-factorization if and only if
n / gcd(d i , n ) is even for at least one generator d i .
v → 2v + 7 construction.
Let (V, ) be an STS(v ). Let (X , ) be a collection of edge-disjoint one-factors in the
complete graph Kv +7 on the set X , and moreover let T be a set of v + 7 triples, which to-
gether with one-factors in form a partition of the edge set of Kv +7. Let = {{vi , x , y } :
vi ∈ V, {x , y } ∈ Fi ∈ }. Then (V ∪X , ∪ ∪T ) is an STS(2v +7) with a subsystem STS(v ).
Another well studied class of Steiner triple systems are projective triple systems. Let
Wm be an (m + 1)-dimensional vector space over F2. Let ⊕ be the operation of vector
addition in Wm . Any two nonzero (m + 1)-vectors x and y determine uniquely a third
vector x ⊕ y in Wm , where addition is performed modulo 2 componentwise. Let every
nonzero vector in Wm+1 be represented by a point in a set V of cardinality 2m+1 − 1.
Every two distinct points, corresponding to x and y, define a unique triple formed by
{x, y, x⊕y}. The STS(2m+1 −1) produced in this way is called a projective triple system and
it is often denoted by PG(m , 2) (just consider the triples as lines in the projective space
over GF(2)). To simplify notation, let every point in V be labeled by an integer whose
binary representation is determined by the coordinates of its corresponding vector. Thus
V (PG(m , 2)) = {1, 2, . . . , 2m+1 − 1}.
A partial triple system PTS(v ) is a pair (V, ), where |V | = v and is a collection of
3-element subsets of V such that each unordered pair of elements of V occurs in at most
one triple of . Let (V, ) be a PTS(v ) and (W, ) be an STS(w ) for which V ⊆ W and
⊆ . Then (W, ) is an embedding of (V, ).
Theorem 15. Any partial triple system PTS(v ) can be embedded in an STS(w ) if w = 1, 3
(mod 6) and w ≥ 2v + 1.
Theorem 16. Let v, w ≡ 1, 3 (mod 6) and v ≥ 2w + 1. Then there exists an STS(v ) contain-
ing an STS(w ) as a subsystem.
Exercise 14.
Apply Skolem construction to get an STS(13).
Exercise 15.
Show that a cyclic STS(9) does not exist.
