Disjoint Intersection Problem For Steiner Triple Systems
Except where reference is made to the work of others, the work described in this thesis is
my own or was done in collaboration with my advisory committee. This thesis does not
include proprietary or classifled information.
Sangeetha Srinivasan
Certiflcate of Approval:
Dean G Hofiman
Professor
Mathematics and Statistics
Chris A Rodger, Chair
Professor
Mathematics and Statistics
Charles C Lindner
Professor
Mathematics and Statistics
Peter D Johnson
Professor
Mathematics and Statistics
Nedret Billor
Associate Professor
Mathematics and Statistics
George T. Flowers
Interim Dean
Graduate School
Disjoint Intersection Problem For Steiner Triple Systems
Sangeetha Srinivasan
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
December 17th, 2007
Disjoint Intersection Problem For Steiner Triple Systems
Sangeetha Srinivasan
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Sangeetha Srinivasan was born on January 30th 1984, in Mayiladuthurai, a small town
in South India. She grew up for the most part in Chennai and flnished high school at Padma
Seshadri Bala Bhavan Senior Secondary School, K. K. Nagar. She went on to pursue
a B.Tech in Electrical and Electronics Engineering at Pondicherry Engineering College,
Pondicherry University from July 2001 to May 2005. Soon after in August 2005, she came
to pursue a PhD in Math at Auburn University, Auburn, Alabama, U.S.A. Sangeetha was
also the recipient of the Baskervill Fellowship, awarded by the College of Sciences and
Mathematics, Auburn University, in Spring 2007.
iv
Thesis Abstract
Disjoint Intersection Problem For Steiner Triple Systems
Sangeetha Srinivasan
Master of Science, December 17th, 2007
(B.Tech., Pondicherry Engineering College, India)
33 Typed Pages
Directed by Chris A Rodger
Let (S;T1) and (S;T2) be two Steiner Triple systems on the set S of symbols with the
set of triples T1 and T2 respectively. They are said to intersect in m blocks if jT1\T2j = m.
Further, if the blocks in jT1 \T2j are pairwise disjoint then (S;T1) and (S;T2) are said to
intersect in m pairwise disjoint blocks and are said to have disjoint intersection.
The Disjoint Intersection Problem for Steiner Triple Systems is to completely determine
Intd(v) =
n
m
flfl
fl9 two Steiner triple systems of order v intersecting in m pairwise disjoint
blocks
o
. Intd(v) was determined by Chee. Here we describe a difierent proof of his result
using a modiflcation of the Bose and Skolem Constructions.
v
Acknowledgments
The author is greatly indebted to her Master?s advisor Dr Chris Rodger for being a
great inspiration and for his patient endurance and understanding in times of di?culties.
She is also grateful to her PhD advisor Dr Dean Hofiman for his unconditional support and
co-operation. She would also like to thank the other committee members Dr Johnson, Dr
Lindner and Dr Billor for their valuable ideas and invaluable time. On a more personal
note, the author is profoundly thankful to her parents, brother and sister for their love and
long standing encouragement. Finally, she would like to thank her husband Aneesh for the
technical and moral support he has tirelessly provided.
vi
Style manual or journal used Journal of Approximation Theory (together with the style
known as \aums"). Bibliography follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally LATEX)
together with the departmental style-flle aums.sty.
vii
Table of Contents
List of Figures ix
1 Introduction 1
1.1 Deflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 History of the Intersection Problem . . . . . . . . . . . . . . . . . . . . . . . 1
2 v ? 3(mod6) 4
2.1 The First System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 The Second System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Modifying the First System . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 The case where v = 6x+3; and int = 2x . . . . . . . . . . . . . . . . . . . 8
3 v ? 1(mod6): All except six cases 11
3.1 The First Half of the System . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 The Other half of the System . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 A Combination of Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Conclusion 23
Bibliography 24
viii
List of Figures
2.1 STS1 and STS2 based on the Bose Construction: v = 21 . . . . . . . . . . 5
2.2 STS1, STS?1 and STS2 based on the Bose construction: v = 21, k = 3 and
int = (v3 ?3) = 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1 STS1, STS?1 and STS2 based on the Skolem construction: v = 19, k = 2
and int = v?16 ?2 = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 A near subsystem of order 9 in STS1 and STS?1 : v = 25 . . . . . . . . . . 16
3.3 A near subsystem of order 9 in STS2 and STS?2 : v = 25 . . . . . . . . . . 17
ix
Chapter 1
Introduction
1.1 Deflnitions
A Steiner Triple System is an ordered pair (S;T), where S is a flnite set of points
or symbols, and T is a set of 3-element subsets of S called triples, such that each pair of
distinct elements of S occurs together in exactly one triple of T. The order of a Steiner
Triple System (S;T) is the size of the set S, denoted by jSj.
Let (S;T1) and (S;T2) be two Steiner Triple Systems on the same of set of symbols S,
with the set of triples T1 and T2 respectively. The two systems are said to intersect in m
triples if jT1\T2j = m. Further, if the triples in T1\T2 are pairwise disjoint, then they are
said to intersect in m pairwise disjoint triples and are said to have disjoint intersection.
The Disjoint Intersection Problem for Steiner Triple Systems is to completely determine
Intd(v) =
n
m
flfl
fl9 two non-trivial Steiner Triple Systems of order v (so v > 1) intersecting
in m pairwise disjoint triples
o
. A related well-studied problem is the Intersection Problem,
which is to determine Int(v) =
n
m
flfl
fl9 two Steiner Triple systems of order v intersecting in
m triples
o
.
1.2 History of the Intersection Problem
The intersection problem for Steiner Triple Systems was completely solved by Lindner
and Rosa [1]. The problem was then generalized to require more of the intersecting triples,
namely that both systems have all the triples containing one specifled point in common.
Such a set of common triples is called a  ower, so this problem was known as the  ower
1
intersection problem. This is also equivalent to solving the Intersection problem for Group
Divisible Designs of block size 3 and group size 2 (that is, f3g?GDDs of the type 2t). This
was solved by Lindner and Hofiman [2].
The Intersection problem has also been studied in other settings such as, Group Divis-
ible Designs of block size 3, having 3 groups of size g (that is, f3g?GDDs of type g3), and
Group Divisible Designs of block size 3 and group size g (that is, f3g?GDDs of type gt).
The former was solved by Fu [3] and the latter was by Butler and Hofiman [4].
In the spirit of requiring more of the intersection triples, Chee [5] specifled that the
intersecting triples also have to be pairwise disjoint. So, in a sense this is at the opposite
end of the spectrum from the  ower intersection problem. This is the Disjoint Intersection
Problem for Steiner Triple Systems and it was completely solved by Chee. He proved that
(recall Intd(v) only considers systems that are non-trivial)
Intd(v) =
8>
<
>:
n
0; 1; :::; v3
o
ifv ? 3(mod6); and
n
0; 1; :::; v?13
o
ifv ? 1(mod6);
except that; Intd(7) = f0; 1g and Intd(9) = f0; 1; 3g:
In this paper, we provide a difierent proof of Chee?s result based on the Bose and
Skolem constructions. The paper is self contained in that these constructions are clear from
the proofs given in this paper; but the interested reader can flnd a good description of these
constructions in [6]. The proof naturally breaks down into several cases, each being covered
in one of the following sections. The cases depend on both the order v and the values of
int 2 Intd(v). Using this method, all except a few of the largest values in Intd(v) are found
2
very quickly (see the next two chapters), using no more than some basic latin squares in
the proof.
The symbols used in the construction often contain Za ?Z3. It helps to think of the
vertices being arranged with a on each of 3 levels; so that the edges (i;j);(i;k) maybe
thought of as being vertical edges. These vertical edges play a pivotal role in the upcoming
sections. We also observe that, Intd(1) = f0g and Intd(3) = f1g.
3
Chapter 2
v ? 3(mod6)
In this chapter it is shown that when v ? 3(mod6), Intd(v)  
n
0; 1; :::; v3 ?1; v3
o
.
Let v = 6x+3, and let the set of symbols be S =Z2x+1 ?Z3.
2.1 The First System
For the flrst system STS1, the set of triples T1 = ?1a [?1b are deflned below according
to the Bose construction and are shown in Figure 2.1. Here, the subscripts a and b denote
the vertical triples and the mixed level triples respectively. Also, in deflning the mixed
level triples, we are using an idempotent commutative quasigroup of order 2x + 1, QB =
(Z2x+1;?), whose entry in the ith row and jth column is denoted by i?j (the subscript B
stands for Bose).
?1a =
nn
(i; 0); (i; 1); (i; 2)
oflfl
fli 2Z2x+1
o
and
?1b =
nn
(i; k); (j; k); (i?j; k +1)
oflfl
fli; j 2Z2x+1; i 6= j; k 2Z3
o
;
reducing the sum modulo 3.
2.2 The Second System
We now deflne the set of triples T2 = ?2a [ ?2b of the second Steiner Triple system,
STS2, such that the two systems STS1 and STS2 intersect in the disjoint set of vertical
triples as shown in Figure 2.1. Hence, 2x+1 = v3 2 Intd(v).
4
b
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
2
0 1 2x
0 1 2x
2
0
1
ba ...
...
Type 2a
Type 1b
Type 2b
STS
Type 1a
1
2
STSa0
Figure 2.1: STS1 and STS2 based on the Bose Construction: v = 21
?2a = ?1a; and
?2b =
nn
(i; k); (j; k); (i?j; k +2)
oflfl
fli; j 2Z2x+1; i 6= j; k 2Z3
o
;
reducing the sum modulo 3:
Thus; T1 \T2 = ?2a = ?1a:
5
2.3 Modifying the First System
We have already shown that v3 2 Intd(v). In order to get the other values in Intd(v), we
make modiflcations in STS1 to get STS?1 with the set of triples T?1 = ??1a[??1b. By breaking
down k > 1 of the vertical triples in STS1, we get v3 ?k 2 Intd(v) as shown in Figure 2.2.
*
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
00
00
11
11
00
00
11
11
00
00
11
11
00
00
11
11
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0 1 2x
2
1
... ba
b0a
0 STS
Type 1aType 1b
0
0 1 ... 2x
Type *1a
1
2
0 1 ... 2x
STSType 2a0
1
2
Type 2b
1
1
2
Type *1b
STS
Figure 2.2: STS1, STS?1 and STS2 based on the Bose construction: v = 21, k = 3 and
int = (v3 ?3) = 4
6
For 0 ? i < k, let fi+(i) = i + 1 (modk) and fi?(i) = i? 1 (modk). (So fi+(i) and
fi?(i) are in f0;1;:::;k?1g). Otherwise, let fi+(i) = fi?(i) = i. Then, the triples in STS?1
are given by;
??1a =
nn
(i; 0); (fi+(i); 1); (i; 2)
oflfl
fli 2Z2x+1
o
;and
??1b =
nn
(i; 0); (j; 0); (fi+(i?j); 1)
oflfl
fli; j 2Z2x+1; i 6= j
o[
nn
(i; 1); (j; 1); (fi?(i?j); 2)
oflfl
fli; j 2Z2x+1; i 6= j
o[
nn
(i; 2); (j; 2); (i?j; 0)
oflfl
fli; j 2Z2x+1; i 6= j
o
:
The main idea is to break down two or more of the vertical triples in STS1, taking
care that the new triples formed are unlike any of the triples in STS2. All the edges from
level 1 to the flrst k vertices on level 2, are cyclically shifted to the right (modulo k). This
is done by the permutation fi+(i). Thus, the flrst k vertical triples are broken up and are
no longer triples, while all the mixed level triples are intact (though some have their vertex
on the lower level shifted). To make the broken triples whole again, we apply a similar
permutation fi?(i) to all the edges going from level 2 to the flrst k vertices of level 3, which
shifts them cyclically to the left (modulo k) this time. Thus, a new set of vertical triples
??1a is formed. The mixed level triples going from the third level to the flrst level remain
unchanged.
In this way, we can break down 2 ? k ? v3 vertical triples of STS1, and hence get
Intd(v)  
n
0; 1; :::; v3 ?2; v3
o
, when v ? 3(mod6). The missing value is dealt with in the
next section.
7
2.4 The case where v = 6x+3; and int = 2x
So far, we have proved that when v ? 3 (mod6), Intd(v)  
n
0; 1; :::; v3 ?2; v3
o
. In
order to get the missing value int = v3 ? 1, we start looking at the cyclic Steiner Triple
System of order 15; the missing value here would be 4 (we don?t start with v = 9 because
the missing value 2 doesn?t exist for this case and for v = 3, the case is trivially not
satisfled). We generate STS2 by simply choosing a difierent base block for the same set
of edge difierences as in STS1. Then, we modify some of the triples in STS1 to get STS?1
such that we achieve the missing value 4 in Intd(15) (shown in Tables 2.1 through 2.4). We
will need the following theorem to conclude our proof.
Table 2.1: Cyclic STS(15): Triples covering edge difierences f1, 3, 4g
STS1 STS?1 STS2
f1, 2, 5g | f1, 4, 5g
f2, 3, 6g | f2, 5, 6g
f3, 4, 7g f3, 4, 7g f3, 6, 7g
f4, 5, 8g f4, 5, 8g f4, 7, 8g
f5, 6, 9g f5, 6, 9g f5, 8, 9g
f6, 7, 10g f6, 7, 10g f6, 9, 10g
f7, 8, 11g f7, 8, 11g f7, 10, 11g
f8, 9, 12g f8, 9, 12g f8, 11, 12g
f9, 10, 13g f9, 10, 13g f9, 12, 13g
f10, 11, 14g f10, 11, 14g f10, 13, 14g
f11, 12, 15g f11, 12, 15g f11, 14, 15g
f12, 13, 1g f12, 13, 1g f12, 15, 1g
f13, 14, 2g f13, 14, 2g f13, 1, 2g
f14, 15, 3g f14, 15, 3g f14, 2, 3g
f15, 1, 4g f15, 1, 4g f15, 3, 4g
8
Table 2.2: Cyclic STS(15): Triples covering edge difierences f2, 6, 7g
STS1 STS?1 STS2
f1, 3, 9g f1, 3, 9g f1, 7, 9g
f2, 4, 10g f2, 4, 10g f2, 8, 10g
f3, 5, 11g | f3, 9, 11g
f4, 6, 12g f4, 6, 12g f4, 10, 12g
f5, 7, 13g f5, 7, 13g f5, 11, 13g
f6, 8, 14g f6, 8, 14g f6, 12, 14g
f7, 9, 15g f7, 9, 15g f7, 13, 15g
f8, 10, 1g f8, 10, 1g f8, 14, 1g
f9, 11, 2g f9, 11, 2g f9, 15, 2g
f10, 12, 3g f10, 12, 3g f10, 1, 3g
f11, 13, 4g f11, 13, 4g f11, 2, 4g
f12, 14, 5g f12, 14, 5g f12, 3, 5g
f13, 15, 6g f13, 15, 6g f13, 4, 6g
f14, 1, 7g f14, 1, 7g f14, 5, 7g
f15, 2, 8g f15, 2, 8g f15, 6, 8g
Table 2.3: Cyclic STS(15): Disjoint set of triples
STS1 STS?1 STS2
f1, 6, 11g | f1, 6, 11g
f2, 7, 12g f2, 7, 12g f2, 7, 12g
f3, 8, 13g f3, 8, 13g f3, 8, 13g
f4, 9, 14g f4, 9, 14g f4, 9, 14g
f5, 10, 15g f5, 10, 15g f5, 10, 15g
Table 2.4: Cyclic STS(15): Newly added triples
STS1 STS?1 STS2
| f1, 6, 2g |
| f6, 11, 3g |
| f11, 1, 5g |
| f2, 3, 5g |
9
Theorem 2.1 (Allan B. Cruse) The necessary and su?cient conditions for embedding
an incomplete symmetric latin square L of order n in a symmetric latin square S of order
t are:
1. NL( ) ? 2n?t for all 1 ?  ? t and
2. The number of symbols occurring on the diagonal of L with the wrong parity (that is
NL( ) not congruent to t(mod2)) is at most t?n.
Consider an idempotent and commutative latin square QB = (Zv3;?) of order v3 ? 10,
which produces a STS(v) formed by the Bose construction. By Cruse?s Theorem 2.1 we can
ensure that QB contains an idempotent and commutative sub-square (Z5;?) of order 5. (To
see this, note that in our case, NL( ) 2 f0;5g and hence we require t ? 2n (by Condition
1). Now, according to whether t is odd or even, the number of symbols with the wrong
parity is 0 or 5. Hence (by Condition 2), t ? 5. But, since our n = 5, this requirement is
already met by the constraint t ? 2n.)
We remove all the triples inZ5?Z3, a subsystem of order 15 in STS1(v) and STS2(v),
and replace them respectively with the triples from STS?1(15) and STS2(15) (obtained from
tables 2.1 through 2.4 and renamed accordingly), to get STS?1(v) and STS?2(v) respectively.
Now, STS?1(v) and STS?2(v) intersect in v3 ?1 disjoint triples.
This leaves us with proving that 6 2 Intd(21) and 8 2 Intd(27). We can use examples
to show that these values exist (The interested reader can obtain these from the appendices
A and B given in [5]).
10
Chapter 3
v ? 1(mod6): All except six cases
In this chapter it is shown that when v = 6x+1, Intd(v)  
n
0; 1; :::; v?13
o
nM, where,
M =
8
>>>>
><
>>>>
>:
f2x?1g if x ? 0(mod3);
f2x?2; 2xg if x ? 1(mod3); and
f2x?3; 2x?1; 2xg if x ? 2(mod3):
Let the set of symbols be S =Z2x ?Z3 [f1g.
3.1 The First Half of the System
For the flrst system STS1, we deflne the set of triples T1 = ?1a [?1b [?1c [?1d [?1e
according to the Skolem construction as shown in Figure 3.1. Here, the subscripts a and b
denote the vertical triples and the mixed level triples respectively, while c, d and e denote
diagonal triples. Also, in deflning the mixed level triples, we are using a half-idempotent
commutative quasigroup of order 2x, QS = (Z2x;?), whose entry in the ith row and jth
column is denoted by i?j (the subscript S stands for Skolem). A quasigroup is said to be
half idempotent if i?i = i when i ? x and i?i = i?x when i > x.
11
?1a =
nn
(i; 0); (i; 1); (i; 2)
oflfl
fli 2Zx
o
?1b =
nn
(i; k); (j; k); (i?j; k +1)
oflfl
fli; j 2Z2x; i 6= j; k 2Z3
o
;
reducing the sum modulo 3:
?1c =
nn
(x+i; 0); (i; 1); 1
oflfl
fli 2Zx
o
?1d =
nn
(x+i; 1); (i; 2); 1
oflfl
fli 2Zx
o
?1e =
nn
(x+i; 2); (i; 0); 1
oflfl
fli 2Zx
o
Similar to the v = 6x + 3 case, we deflne the triples of the second system STS2, such
that the two systems intersect in the disjoint set of x vertical triples, namely, ?2a = ?1a.
?2a = ?1a;
?2b =
nn
(i; k); (j; k); (i?j; k +2)
oflfl
fli; j 2Z2x; i 6= j; k 2Z3
o
;
reducing the sum modulo 3:
?2c =
nn
(x+i; 0); (i; 2); 1
oflfl
fli 2Zx
o
?2d =
nn
(x+i; 1); (i; 0); 1
oflfl
fli 2Zx
o
?2e =
nn
(x+i; 2); (i; 1); 1
oflfl
fli 2Zx
o
We then use permutations, just like in the v = 6x + 3 case, on the flrst x vertical
triples of STS1 (or the flrst half of the system) to get STS?1. By breaking down k (where
x ? k > 1) of the vertical triples in STS1, we get x?k = v?16 ?k 2 Intd(v).
12
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
Type a
Type b
Type c
Type d
Type e
STS
0
1
2
a
a0b
b 0
1
2
x?1 x10 x+1 2x?1
STS
a
a0b
b 0
1
2
x?1 x10 x+1 2x?1
STS
0 1 x?1 x x+1 2x?1
... ...
......
......
1
2
*
Figure 3.1: STS1, STS?1 and STS2 based on the Skolem construction: v = 19, k = 2 and
int = v?16 ?2 = 1
13
The strategy behind the following choice of triples for STS?1 is the same as described in
Section 2.3. Here we need to take care that all the edges from level 1 to the flrst k vertices
on level 2, are cyclically shifted to the right (modulo k) by the permutation fi+(i); and a
similar permutation fi?(i) shifts all the edges going from level 2 to the flrst k vertices of
level 3 cyclically to the left (modulo k) this time. We notice that ??1e = ?1e, and the mixed
level triples containing edges joining vertices on the third level to vertices on the flrst level
remain unchanged.
If fi+(i) and fi?(i) are as deflned in Section 2.3, then the triples in STS?1 are;
??1a =
nn
(i; 0); (fi+(i); 1); (i; 2)
oflfl
fli 2Zx
o
??1b =
nn
(i; 0); (j; 0); (fi+(i?j); 1)
oflfl
fli; j 2Z2x; i 6= j
o[
nn
(i; 1); (j; 1); (fi?(i?j); 2)
oflfl
fli; j 2Z2x; i 6= j
o[
nn
(i; 2); (j; 2); (i?j; 0)
oflfl
fli; j 2Z2x; i 6= j
o
;
??1c =
nn
(x+i; 0); (fi+(i); 1); 1
oflfl
fli 2Zx
o
??1d =
nn
(x+i; 1); (fi?(i); 2); 1
oflfl
fli 2Zx
o
??1e =?1e
This procedure shows that
n
0; 1; :::; v?16 ? 2; v?16
o
 Intd(v). The missing value
v?1
6 ?1 occurs because we can?t break apart only one of the vertical triples (hence we require
k > 1).
14
3.2 The Other half of the System
To get most of the larger values in Intd(v), in this section we introduce a method where
we create, then break down, vertex-disjoint near subsystems of order 9 in the right half of
STS1 and STS2. The modifled systems, labeled STS?1 and STS?2, are deflned such that we
get either 0 or 3 additional disjoint triples per near subsystem in their intersection.
Before we get to work on the triples in a near subsystem, we need to create appropriate
near subsystems; that is, we need sets of 9 triples on 9 vertices in the right halves of STS1
and STS2. In graph theoretical terminology, each near subsystem is formed from K9 by
removing a particular parallel class. This can be achieved by manipulating the quasigroup
of order 2x as shown in Figures 3.2 and 3.3.
While manipulating the quasigroup QS we note that such an embedding of a 3 ? 3
incomplete latin square in one of order 2x is possible as long as x ? 3, by Cruse?s Theorem
(Theorem 2.1). We can extend the argument to make more than one near subsystem of
order 9 on the right half of the system, each arising from its own 3 ? 3 incomplete latin
square. (To see that we can incorporate s ? x3 such 3 ? 3 disjoint squares, note that in
our case, NL( ) 2f0; 1; 2g and hence we require t ? 2s (by Condition 1 of Theorem 2.1).
Also, t is always even and the number of symbols with the wrong parity is 3s. Hence (by
Condition 2 of Theorem 2.1), t ? 3s; this requirement is already met by the constraint
t = 2x.)
More formally, for 0 ? s ? x3, let QS = (Z2x;?) be the half-idempotent commutative
quasigroup (used in the Skolem construction for v = 6x+1) which for 1 ? i ? s contains the
following 4 sub-squares deflned by the operators ?i, ?(i; 0), ?(i; 1) and ?(i; 2). Let B(1; i) and
B(2; i) each represent a set of 9 triples on the symbols fx+3i?3; x+3i?2; x+3i?1g?Z3
15
2x?1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0 2x?1x?11 x+2... x
1
2
x+2...x+1xx?1...10
...
0
x+1
Near Subsystem of order 9
2x?1
Half Idempotent Commutative Quasigroup of Order 2x
SQ   =
STS B1* (1, i)
B*(1, i)
0 ...
xx+1
x+2
x+1x
21x
0x+2
x+1
x+2x+1x1
1001
x?1
STS1
0
1
2
x?1x?1
2x?1 x?1
x+2
Figure 3.2: A near subsystem of order 9 in STS1 and STS?1 : v = 25
16
x?1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
00
00
11
11
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
00
11
11
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0 2x?1x?11 x+2... x
1
2
x+2...x+1xx?1...10
...
0
x+1
...
1
0
xx+1
x+2
0 1
2
0 1
2
0 1
2
x
x
x
x
x+1
x+1
x+1
x+1
x+1
x
x+2
x+2
x+2
x+2
x+2
x+2
Level 0 to 2
Level 1 to 0
Level 2 to 1
Near Subsystem of order 9
2x?1
Q   =S
B
STS
STS
Half Idempotent Commutative Quasigroup of Order 2x
2
2* (2, i)
B(2, i)*
x+1
x
0
1
2
2x?1
xx?1
1
100
x?1x?1
x+1x+2 2x?1
Figure 3.3: A near subsystem of order 9 in STS2 and STS?2 : v = 25
17
for the ith near subsystem in STS1 and STS2 respectively. B(1; i) and B(2; i) are given as
follows.
B(1; i) =
n
(p; l); (q; l); (p?i q; l +1)
flfl
fll 2Z3; x+3i?3 ? p < q ? x+3i?1
o
; and
B(2; i) =
n
(p; l); (q; l); (p?(i; l) q; l?1)
flfl
fll 2Z3; x+3i?3 ? p < q ? x+3i?1
o
;
reducing the sums (l +1) and (l +2) modulo 3.
?i x+3i?3 x+3i?2 x+3i?1
x+3i?3 3i?3 x+3i?1 x+3i?2
x+3i?2 x+3i?1 3i?2 x+3i?3
x+3i?1 x+3i?2 x+3i?3 3i?1
?i; 0 x+3i?3 x+3i?2 x+3i?1
x+3i?3 3i?3 x+3i?3 x+3i?1
x+3i?2 x+3i?3 3i?2 x+3i?2
x+3i?1 x+3i?1 x+3i?2 3i?1
?i; 1 x+3i?3 x+3i?2 x+3i?1
x+3i?3 3i?3 x+3i?1 x+3i?2
x+3i?2 x+3i?1 3i?2 x+3i?3
x+3i?1 x+3i?2 x+3i?3 3i?1
We then remove the set of triples B(1; i) and B(2; i) from STS1 and STS2 and replace
them with B?(1; i) and B?(2; i) to form STS?1 and STS?2 respectively. STS?1 and STS?2 are the
required Steiner Triple Systems Intersecting in 3s disjoint triples, where s is the number of
18
?i; 2 x+3i?3 x+3i?2 x+3i?1
x+3i?3 3i?3 x+3i?2 x+3i?3
x+3i?2 x+3i?2 3i?2 x+3i?1
x+3i?1 x+3i?3 x+3i?1 3i?1
near subsystems formed. B?(1; i) and B?(2; i) are given as follows.
B?(1; i) =
n
(p; l); (q; l); (r; l)
flfl
fll 2Z3; x+3i?3 ? p < q < r ? x+3i?1
o[
n
(p; l); (p+1; l +1); (p+2; l +2)
flfl
flp = x+3i?3; l 2Z3
o[
n
(p; l); (p?1; l +1); (p?2; l +2)
flfl
flp = x+3i?1; l 2Z3
o
;
reducing the sums (l +1) and (l +2) modulo 3, and
B?(2; i) =
n
(p; l); (q; l); (r; l)
flfl
fll 2Z3; x+3i?3 ? p < q < r ? x+3i?1
o[
n
(p+1; l); (p; l +1); (p; l +2)
flfl
flp = x+3i?3; l 2Z3
o[
n
(p; l); (p?2; l +1); (p; l +2)
flfl
flp = x+3i?1; l 2Z3
o
;
reducing the sums (l +1) and (l +2) modulo 3.
3.3 A Combination of Techniques
We can use a combination of the methods explained above (in Sections 3.1 and 3.2) in
order to get almost all of the intermediate values, leaving us with the following exceptions
when v = 6x+1:
int 6=
8
>>>>
><
>>>>
>:
f2x?1g if x ? 0(mod3)
f2x?2; 2xg if x ? 1(mod3)
f2x?3; 2x?1; 2xg if x ? 2(mod3)
19
Exceptions occur due to the combined limitations of our techniques on the right and
left halves of the triple system. On the left we can?t achieve int = x ? 1. Since we can
achieve disjoint intersections only in multiples of 3 from the right half of the system, if
x ? 1or2(mod3), we can?t get disjoint intersections (x?1)or(x?2) respectively from the
right half alone.
Table 3.1: x ? 0(mod3)
To realise an intersection int, break down k vertical triples in the left half, and for
1 ? i ? s, replace B(1; i) and B(2; i) with B?(1; i) and B?(2; i) respectively in the right half.
int k s Exceptions
0;1;:::;x?2;x x;x?1;:::;2;0 | |
x?1 4 1 v = 19
2x;2x?2;:::;x+i;:::;x+1 0;2;:::;x?i;:::;x?1 x3 |
2x?1 | | v ? 19
The ensuing discussion is summarized in Table 3.1. When x ? 0 (mod3), (that is,
when x = f0; 3; 6; 9; ::: g and so v = f1; 19; 37; 55; ::: g), we can always have
at least one near subsystem of order 9 on the right (except when v = 1; which is not a
concern since there are no triples in an STS(1) to begin with). We already know how to get
int 2f0; 1; 2; :::; x?2; xg from Section 3.1. To get int = x?1, we use the construction
from Section 3.1 where k = 4 (giving x ? 4 disjoint triples on the left), combined with
3 disjoint triples in the intersection from the right half using exactly s = 1 of the near
subsystems explained in Section 3.2. The exception here will be v = 19, where there are
not enough triples on the left, since k = 4 > x = 3. Now, to get int 2 f2x ? 1; 2x ?
3; :::; x+i; :::; x+ 2; x+ 1g, we use s = x3 near subsystems to get x disjoint triples in
the intersection on the right half. We also use the construction in Section 3.1 (on the left
20
half of the system) with k = f0; 2; :::; x?i; :::; x?2; x?1g corresponding respectively
to each of the values in int. Finally, we note that no combination of the techniques in
Sections 3.1 and 3.2 can get the value int = 2x?1.
Using arguments similar to those described above and inputs from the following ta-
bles one can achieve all the required disjoint intersection values except if (v; int) 2 E =
n
(7; 0); (13; 1); (19; 1); (13; 3)
o
. Note that in the following tables, k stands for the num-
ber of triples to be broken down in the construction from Section 3.1 and s represents the
number of near subsystems to be altered by the construction in Section 3.2. The exceptional
cases in E are considered below.
Table 3.2: x ? 1(mod3)
To realise an intersection int, break down k vertical triples in the left half, and for
1 ? i ? s, replace B(1; i) and B(2; i) with B?(1; i) and B?(2; i) respectively in the right half.
int k s Exceptions
0;1;:::;x?2;x x;x?1;:::;2;0 | |
x?1 4 1 v = 7
2x?1;2x?3;:::;x+i;:::;x+1 0;2;:::;x?i?1;:::;x?2 x?13 |
2x?2 | | v ? 7
2x | | v ? 25
When (v; int) = (7; 0), let the set of symbols beZ7. Consider the cyclic Steiner Triple
System with base block f0; 1; 3g as STS1. For the same set of symbols, we take the base
block as f0; 6; 4g and generate the rest of the 6 triples for STS2, such that STS1 and
STS2 intersect in none of the blocks.
When (v; int) = (13; 1), let the cyclic Steiner Triple System of order 13 on the set
of symbols Z13 with base blocks f0; 1; 4g and f0; 2; 7g represent STS1. We choose
21
Table 3.3: x ? 2(mod3)
To realise an intersection int, break down k vertical triples in the left half, and for
1 ? i ? s, replace B(1; i) and B(2; i) with B?(1; i) and B?(2; i) respectively in the right half.
int k s Exceptions
0;1;:::;x?2;x x;x?1;:::;2;0 | |
x?1 4 1 v = 13
2x?2;2x?4;:::;x+i;:::;x+1 0;2;:::;x?i?2;:::;x?3 x?23 v = 13
2x?3 | | v ? 13
2x?1 | | v ? 13
2x | | v ? 13
difierent base blocks f0; 1; 10g and f0; 2; 8g to generate STS2, such that STS1 and STS2
intersect in none of the triples. We apply the permutation fi = (7 8) on the vertices of STS2
to achieve STS?2. Then, STS1 and STS?2 intersect in exactly one disjoint triple (namely,
f0; 2; 7g). When (v; int) = (13; 3), we apply the permutation fi0 = (7 9 8 )(11 12) on
the vertices of STS2 to achieve STS?2. Now, STS1 and STS?2 intersect in 3 disjoint triples
(namely, f0; 2; 7g, f1; 3; 8g and f4; 6; 11g).
Similarly, when (v; int) = (19; 1), let the cyclic Steiner Triple System of order 19 on
the set of symbolsZ19 with base blocks f0; 1; 5g, f0; 2; 8g and f0; 3; 10g represent STS1.
We choose difierent base blocks f0; 1; 15g, f0; 2; 13g and f0; 3; 12g to generate STS2,
such that STS1 and STS2 intersect in none of the triples. Then, we apply the permutation
fi00 = (10 12) on the vertices of STS2 to achieve STS?2. Now, STS1 and STS?2 intersect in
exactly one disjoint triple (namely, f0; 3; 10g).
22
Chapter 4
Conclusion
Thus we have shown a difierent proof of Chee?s result (Conditions 4.1 and 4.2) for the
Disjoint Intersection problem, except possibly for a few cases given by Condition 4.3. The
main advantage of our method is that Intd(v) is determined very quickly and easily. In this
thesis we have shown that
Intd(v) =
8>
<
>:
n
0; 1; :::; v3
o
ifv ? 3(mod6); and
n
0; 1; :::; v?13
o
ifv ? 1(mod6);
(4.1)
except that, Intd(7) = f0; 1g; Intd(9) = f0; 1; 3g;and except whether or not (4.2)
Intd(6x+1) ?
8>
>>>
><
>>>
>>:
f2x?1g if x ? 0(mod3);
f2x?2; 2xg if x ? 1(mod3); and
f2x?3; 2x?1; 2xg if x ? 2(mod3):
(4.3)
23
Bibliography
[1] C. C. Lindner and A. Rosa: Steiner Triple Systems with a prescribed number of triples
in common. Canad. J. Math. 27 (1975), 1166-1175.
[2] D. G. Hofiman and C. C. Lindner: The Flower intersection problem for Steiner triple
systems. Ann. Discrete Math. 34 (1987), 243-258.
[3] H. L. Fu: On the construction of certain types of Latin Squares with prescribed intersec-
tions. PhD thesis, Department of Discrete and Statistical Sciences, Auburn University,
Auburn, Alabama, (1980).
[4] R. A. R. Butler and D. G. Hofiman: Intersections of group divisible triple systems. Ars
Combin. 34 (1992), 268-288.
[5] Y. M. Chee Steiner Triple systems intersecting in Pairwise Disjoint Blocks. The Elec-
tronic J. of Combin. 11 (2004), #R27.
[6] C. C. Lindner, C. A. Rodger: Design Theory. CRC Press LLC (1997), 1-13.
24