The Intersection Problem for Steiner Triple Systems
by
Whitney Koetter
A thesis submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Master of Science
Auburn, Alabama
December 12, 2011
Keywords: Steiner triple system, intersection problem
Copyright 2011 by Whitney Koetter
Approved by
Charles Lindner, Chair, Professor of Mathematics
Peter Johnson, Professor of Mathematics
Dean Ho man, Professor of Mathematics
Abstract
In this thesis we give a new solution to the intersection problem for Steiner triple systems,
using results that were not available when the original solution was given. In particular
we show for each pair (n;k), where n  1 or 3 (mod 6)  19 and k 2f0;1;2;:::;x =
n(n 1)
6 gnfx 1;x 2;x 3;x 5g, the existence of a pair of Steiner triple systems (S,T1)
and (S,T2) of order n with the property that jT1\T2j= k.
ii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
1 Introduction and outline of the thesis . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Necessary Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 The Original Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 The intersection of quasigroups . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5 The 6n+ 1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6 The 6n+ 3 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
iii
Chapter 1
Introduction and outline of the thesis
A Steiner triple system (STS) of order n is a pair (X,T) where T is a collection of edge
disjoint triangles (or triples) which partitions the edge set of Kn with vertex set X.
Example 1.1 (two triple systems of order 7).
1 2
3
45
6
7
1
23
1
45
1
674
62
5
63
4
73 5
2 7
1 2
3
45
6
7
4
1 6
5
1 7
4
2 71
3 2
6
2 5
5
3 47
3 6
It is immediate that the two triples in this example have exactly one triple in common,
namely
1
23 which we will denote by f1;2;3g.
1
In general we will denote the triangle
a
bc by fa;b;cg.
In this thesis, we will be looking at the intersection problem for Steiner triple systems.
It is well-known that the spectrum for Steiner triple systems is precisely the set of all
n 1 or 3 (mod 6) [3] and that if (X,T) is a triple system of order n, jTj= n(n 1)6 .
Hence the following problem:
THE INTERSECTION PROBLEM: For each n 1 or 3 (mod 6), determine the set of
all k such that there exists a pair of STS(n) having exactly k triples in common.
The two triple systems in Example 1.1 have exactly one triple in common; namely
f1;2;3g.
Now, it turns out that a necessary condition for a pair of STS(n) to have k triples in
common is k2I(n) =f0;1;2;:::;x = n(n 1)6 gnfx 1;x 2;x 3;x 5g. This will be proved
in Chapter 2. It also turns out that except for n = 9, this necessary condition is su cient.
Denote by J(n) =fk such that there exists two STS(n) having k triples in commong. The
following Theorem is due to C.C. Lindner and A. Rosa [5].
Theorem 1.2 J(n) = I(n) for all n 1 or 3 (mod 6), except for J(9). In this case
J(9) =f0;1;2;3;4;6;12g [4].  
The following is an example showing J(7) = I(7) =f0;1;3;7g.
Example 1.3 (J(7) = I(7)).
124
235
346
457
561
672
713
?
126
237
341
452
563
674
715
=?
2
6745 5746 5647 5746 5647 6745? =1
1 2 3 1 2 3
6745 5647 5746 6745 5746 5647? =3
1 2 3 1 2 3
Any STS(7) intersects with itself in 7 triples.
3
Chapter 2
Necessary Conditions
In this section we show that a necessary condition for a pair of triple systems (S,T1) and
(S,T2) of order n to have k triples in common is for k 2f0;1;2;3;4;:::;x = n(n 1)6 gnfx 
1;x 2;x 3;x 5g. A partial triple system of order n is a pair (S,P) where P is a collection
of edge disjoint triples of the edge set of Kn with vertex set S.
Example 2.1 (partial triple system of order 6)
K6
1 1
4635 2 2
3645
P1=
Two partial triple systems (S,P1) and (S,P2) are said to be balanced provided P1 and
P2 cover the same edges. Let P1 be the collection of triples in Example 2.1 and P2 be the
following collection of triples.
Example 2.2 (partial triple systems of order 6)
P2=
1 1
3645 2 2
4635
4
Then P1 and P2 are balanced. It is also the case that P1 and P2 are disjoint, that is, they
have no triples in common.
Now let (S,T1) and (S,T2) be a pair of triple systems of order n. Then the partial triple
systems (S,T1n(T1\T2)) and (S,T2n(T1\T2)) are balanced and disjoint. We will show that
there does not exist a pair of balanced and disjoint partial triple systems containing 1,2,3,
or 5 triples. It follows thatjT1n(T1\T2)j=2f1,2,3,5gand sojT1\T2j=2fn(n 1)6 = x 1;x 
2;x 3;x 5g. It follows thatjT1\T2j2f0;1;2;:::;n(n 1)6 = xgnfx 1;x 2;x 3;x 5g
is a necessary condition for a pair of triple systems to have x triples in common.
To begin, if (S, P1) and (S, P2) are balance and disjoint, every vertex must belong to
at least 2 triples in both P1 and P2. Supposefx;y;zg2P1 and is the only triple containing
x. Then x has degree 2 in P1. Now, in P2 we must have a triple of the form fx;y;ag since
the edge fx;yg has to be covered. However, if a6= z, then the edge fx;ag must be covered
in P1, so x has to have degee at least 4.
b
y
x
a negationslash=zyz
x
a
P1 P2
Now let (S, P1) and (S, P2) be a pair of partial balanced and disjoint triple systems.
Since every vertex in P1 must have degree at least 4 we cannot have jP1j=jP2j2f1;2;3g.
We now show that we cannot have
1. jP1\P2j= 5, and
2. P1 and P2 are balanced
To begin,jSjmust be at least 6, otherwise we could not cover 15 edges. However, since
a maximum partitioning of K6 contains 4 triples, we cannot have jSj= 6.
5
Construct the following incidence matrix
1234. . . . . . i. . . . . . . . . n
t1
t2
t3
t4
t5
I= 1,ifi?t,0,otherwise.{
Then I contains 15 ones. Since each vertex belongs to at least 2 triples we must have
2n 15 so, n 152 , and so n = 7.
It is now clear that I looks like
1 2 3 4 5 6 7
t1
t2
t3
t4
t5
1
1
1
1 1
1
1
1
1
1
1
1
1
1
1
This is to say exactly one vertex belongs to 3 triples and the rest to 2 triples. It follows
that P1 looks like
7
2
4
65
3
1
6
These edges cannot be covered by 5 disjoint triples, and so, we have the following result:
Lemma 2.3 A necessary condition for a pair of triple systems (S,T1) and (S,T2) of order
n to have k triples in common is for k2f0;1;2;3;:::;n(n 1)6 = xgnfx 1;x 2;x 3;x 5g.
 
In [5] this was shown to be su cient for all n 1 or 3 (mod 6), except for n = 9. In
this case the intersection numbers are f0,1,2,3,4,6,12g [4].
The object of this thesis is a di erent and much simpler proof of the intersection problem.
We will  rst sketch a proof of the original solution. We then give a new construction using
results which were not available when the original paper was written.
7
Chapter 3
The Original Construction
This chapter will give a brief sketch of the original solution of the intersection problem
[5]. The interested reader is referenced to the original paper for details. The original solution
uses the following two constructions.
The 2n+ 1 Construction: Let (S,T) be a STS(n) and (X,F), F = fF1;F2;:::;Fng, a
1-factorization of Kn+1 with vertex set X, where X \ S = ;. Let S = S [ X and de ne a
collection of triples T as follows
1. T  T , and
2. let  be any 1-1 mapping from S onto f1;2;3;:::;ng. For each x2 S and each
fa;bg2Fx place the triple fx;a;bg in T .
Then (S ;T ) is a STS(2n+ 1)
F1? F2? Fx? Fn
Kn=
STS(n) x
a b
8
The 2n+ 7 Construction: LetF =fF1;F2;:::;Fng be a collection of n 1-factors of Kn+7
with vertex set X. Further let K = Kn+7nF and K1 and K2 two partitions of K into n + 7
triples, where K1\K2 =;. Now let (S,T) be a STS(n) with vertex set S, such that
S \ X = ;. Set S = S[ X and de ne a collection of triples T as follows:
1. T  T ,
2. Ki T , where i = 1 or 2 (but not both), and
3. let  be any 1-1 mapping from S onto f1;2;3;:::;ng. For each x2 S and each
fa;bg2Fx place the triple fx;a;bg in T . Then (S ;T ) is a STS(2n+ 7).
F1? F2? Fx? Fn?
Kn+7=
STS(n) x
a b
=Ki
The Original Construction
1. Ad hoc constructions are used to solve the problem for all n 33. So we can assume
n 37.
2. Every m 1 or 3 (mod 6) can be written in the form 2n + 1 or 2n + 7, where n 1
or 3 (mod 6).
3. The proof uses induction. So assume we have solved the intersection problem for all
n 1 or 3 (mod 6)  33.
9
4. If n 1(mod6) we use the 2n+ 1 Construction:
Let (S,T1) and (S,T2) be any two STS(n), F a 1-factorization of Kn+1, and  and  
1-1 mappings from S onto f1;2;3;:::;ng. Then,
F1? F2? Fn?
(S,T1)
F1? F2? Fn?
(S,T2)
?
= jT1\T2j + PjFi \Fi j. A bit of re ection shows that I(2n+ 1) = J(2n+ 1).
5. If n 3 (mod 6) use the 2n+ 7 construction.
Let (S,T1) and (S,T2) be any two STS(n), F a collection of n 1-factors of Kn+7, and  
and  1-1 mappings from S onto f1;2;3;:::;ng Then,
F1? F2? Fn?
(S,T1)
F1? F2? Fn?
(S,T2)
?
Ki Kj
=jT1\T2j + PjF1 \Fi j + jKi\Kjj. As with the 2n + 1 Construction it is quite
easy to show that I(2n+ 7) = J(2n+ 7).
With the original construction out of the way we can now proceed to a completly
di erent and new construction.
10
Chapter 4
The intersection of quasigroups
Two quasigroups (Q, 1) and (Q, 2) are said to intersect in k products provided their
tables agree in exactly k cells.
Example 4.1 (Two quasigroups of order 4 intersecting in 6 products).
1 2 3 4
1
2
3
4
?1 1 2 3 41
2
3
4
?21 3 4 2
4 2 1 3
2 4 3 1
3 1 2 4
1 4 2 3
3 2 1 4
2 3 4 1
4 1 3 2
In [2] H.L Fu proved the following theorem.
Theorem 4.2 (H.L. Fu[2]) If n 5, there exists a pair of quasigroups having k products
in common if and only if k2f0;1;2;:::;n2gnfn2 1;n2 2;n2 3;n2 5g.  
Let Q = f1;2;:::;2ng and let H = fh1;h2;:::;hng be a partition of Q into 2-element
subsets (called holes of size 2).
Let (Q,  ) be a quasigroup with the property that (hi; ) is a subgroup for every hole
hi2H. Then (not too surprisingly) (Q,  ) is said to be a quasigroup with holes H.
Two communitive quasigroups (Q, 1) and (Q, 2) with the same holes H are said to
intersect in k products provided their tables agree in exactly k cells above the holes.
11
Example 4.3 (Two communitive quasigroups of order 6 with holes intersecting in 8
products)
1 2 3 4 5 61
23
45
6
?1 1 2 3 4 5 61
23
45
6
?21 2 5 6 4 3
2 1 6 5 3 45 6 3 4 2 1
6 5 4 3 1 24 3
2 1 5 63 4 1 2 6 5
1 2
2 1 3 4
4 3 5 6
6 5
6 5
5 6
4 33 4
6 5
5 64 3
3 4 1 22 1
2 11 2
The following theorem is due to C.M Fu [1].
Theorem 4.4 (C.M Fu [1]) If 2n 10, there exists a pair of commutative quasigroups of
order 2n having the same holes intersecting in k products if and only if
k 2f0;1;2;:::;x = 2n(n 1)gnfx 1;x 2;x 3;x 5g.  
The results in Theorems 4.2 and 4.3 were obtained many years after the original solution
of the intersection problem for Steiner triple systems. We can now use the results in these
two theorems to give a new and much easier solution to this problem.
12
Chapter 5
The 6n+ 1 Construction
In this chapter we will give a 6n + 1 Construction along with the results in Theorems
4.2 and 4.4 to give a new solution of the intersection problem for all 6n + 1  19. We will
give two examples before giving the general construction.
Example 5.1 (n = 19)
Write n = 3 6 + 1. Let jQj= 6 and set S =f1g[(Q f1;2;3g). Let (S,T1) and (S,T2)
be two STS(19)s de ned by:
?
x
y
z
?1 y
x z
({?}?Q,T11)
({?}?Q,T12)
({?}?Q,T13)
T1
STS(7) (Q,?1)
{0,1,3,7}
and
?
a
b
c
?2 b
a c
({?}?Q,T21)
({?}?Q,T22)
({?}?Q,T23)
T2
STS(7) (Q,?2)
?{0,1,2,...,36}\{35,34,33,31}
13
It is a straightforward computation to see that any number n2f0;1;2;:::;57gn
f56;55;54;52gcan be written in the formjT11\T21j+jT12\T22j+jT13\T23j+j(Q; 1)\
(Q; 2)j.
Example 5.2 (n = 25)
Write n = 3 8 + 1. Let jQj = 8, set S =f1g[(Q f1;2;3g), and proceed exactly as in
Example 5.1
The solution for 6n + 1  31
Write 6n + 1 = 3(2n) + 1(2n 10), let jQj = 2n, and set S = f1g[(Q f1;2;3g). Let
(S;T1) and (S;T2) be STS(6n+ 1) de ned as follows:
?
x y a b
c
Foreachhole
(S,T1i)
?i 121
2
a
a
b
b
2n
2n
c
c
xy=yxquasigroup
(Q,?i)withholesh
1,h2,...,hn
hi={x,y}
T1
Where (Q, 1) is used between levels 1 and 2, (Q, 2) is used between levels 2 and 3, and
(Q, 3) is used between levels 3 and 1.
14
?
x y c d
l
hi={x,y}
(S,T2i)
?i 121
2
d
d
c
c
2n
2n
l
l
xy=yxquasigroup
(Q,?i)withholesh
1,h2,...,hn
Foreachhole
T2
Where (Q, 1) is used between levels 1 and 2, (Q, 2) is used between levels 2 and 3, and
(Q, 3) is used between levels 3 and 1.
As in the above two examples it is easy to see that any number
m2I(n) can be written in the form
PjT
1i\T2ij+j(Q; 1)\(Q; 1)j+j(Q; 2)\(Q; 2)j+j(Q; 3)\(Q; 3)j. We will illistrate
this with an example.
Example 5.3 (Two STS(31)s intersecting in 87 triples).
1. Take jT1i\T2ij= 7, for i = 1;2;3;4;5;
2. j(Q; 1)\(Q; 1)j= 40 between Q f1g and Q f2g; and
3. j(Q; 2)\(Q; 2)j= 12 between Q f2g and Q f3g.
4. j(Q; 3)\(Q; 3)j= 0 between Q f3g and Q f1g.
Then PjT1i \T2ij + j(Q; 1) \ (Q; 1)j + j(Q; 2) \ (Q; 2)j + j(Q; 3) \ (Q; 3)j =
35 + 40 + 12 + 0 = 87
15
Summary Examples 5.1, 5.2, and the 6n+1 31 Construction gives a complete solution
of the intersection problem for all 6n + 1  19. As previously mentioned, the case of
6n+ 1 = 13 is handled by an ad hoc construction in the original paper[5].
16
Chapter 6
The 6n+ 3 Construction
It is well known that I(9) = f0;1;2;3;4;6;12g and I(15) = J(15). So we will begin
with examples for 21 and 27, which cannot be done in general with the 6n+ 3 Construction.
Example 6.1 (n = 21)
Let Q be a set of size 7 and set S = Q  f1;2;3g. De ne two STS(21)s (S,T1) and (S,T2) as
follows:
T1
x
y
z
?1 y
x z
(Q,T11)
(Q,T12)
(Q,T13)
STS(7)
(Q,?1)aquasigroupoforder7.
T2
a
b
c
?2 b
a c
(Q,T21)
(Q,T22)
(Q,T23) (Q,?
2)aquasigroupoforder7.
STS(7)
Then if k2f0;1;2;:::;70gnf69;68;67;65g;k = jT11\T21j+jT12\T22j+jT13\T23j+
j(Q; 1)\(Q; 2)j.
Example 6.2 (n = 27)
Let Q be a set of size 9 and set S = Q f1;2;3g. De ne two STS(27) (S,T1) and (S,T2) and
proceed as in Example 6.1
17
The solution for 6n+3  33 Write 6n+ 3 = 3 + 3 2n and let Q be a set of size 2n
with holes H =fh1;h2;:::;hng of size 2. Set S =f11;12;13g[(Q f1;2;3g) and de ne
two STS(6n+ 3)s, (S,T1) and (S,T2) as follows:
T1
T11 T12 T13
AnySTS(9)
x y
z
?1?2 ?3 T1n
STS(9)containing{?1,?2,?3}
?i 12 2ny
x z
xy=yxquasigroup(Q,?i)withholesH={h
1,h2,...,hn}.
Where (Q, 1) is used between levels 1 and 2, (Q, 2) is used between levels 2 and 3, and
(Q, 3) is used between levels 3 and 1.
18
T2
T21 T22 T23
AnySTS(9)
a b
c
?1?2 ?3 T2n
STS(9)containing{?1,?2,?3}
?i 12 2nb
a c
xy=yxquasigroup(Q,?i).withholesH={h
1,h2,...,hn}.
Where (Q, 1) is used between levels 1 and 2, (Q, 2) is used between levels 2 and 3, and
(Q, 3) is used between levels 3 and 1.
Now, let m2I(6n+3). Then m =jT11\T21j+Pj(T1i\T2i)nf11;12;13gj+j(Q; 1)\
(Q; 1)j(between levels 1 and 2) +j(Q; 2) \ (Q; 2)j(between levels 2 and 3)+j(Q; 3) \
(Q; 3)j(between levels 3 and 1).
We illustrate this construction for 6n+ 3 = 33.
19
Example 6.3 (A pair of STS(33) intersecting in 102 triples).
TakejT11\T21j= 0 eachj(T1inf11;12;13gj= 0 (this is simply a pair of triple systems
of order 9 having just the triple f11;12;13g in common, j(Q; 1)\(Q; 1)j= 40 between
levels 1 and 2 and 2 and 3, and j(Q; 3)\(Q; 3)j= 22 between levels 3 and 1.
Summary In this chapter we have given a complete solution of the intersection problem
for all n 3(mod 6)  21.
20
Chapter 7
Concluding remarks
In this thesis we have given a new solution to the intersection problem for Steiner triple
systems using results that were not available when the original solution was obtained. In
particular we have given a new solution for all n 1 or 3(mod 6) 19. Our solution is much
simpler than the original solution and has the added bene t of not using induction.
21
Bibliography
[1] C.M. Fu, The intersection problem for pentagon systems, Ph D thesis, Auburn Univer-
sity, (1987).
[2] H.L. Fu, On the construction of certain types of latin squares with prescribed interse-
ctions, Ph D thesis, Auburn University, (1980)
[3] T.P. Kirkman, On a problem in combinations, Cambridge and Dublin Math, J.,2(1847),
191-204.
[4] E.S. Kramer and D.M. Messner, Intersections among Steiner systems, J. Combinatorial
Theory A, 16(1974), 273-285.
[5] C.C. Lindner and A. Rosa, Steiner triple systems having a prescribed number of tripples
in common, Carnad J. Math., 27(1975), 1166-1175.
22