A New Solution to the Intersection Problem
of Mendelsohn Triple Systems
by
Rachel Watson
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
May 7, 2012
Keywords: Mendelsohn triple system, intersection problem, cyclic triple
Copyright 2012 by Rachel Watson
Approved by
Charles Lindner, Chair, Professor of Mathematics
Chris Rodger, Professor of Mathematics
Peter Johnson, Professor of Mathematics
Dean Ho man, Professor of Mathematics
Abstract
This thesis gives a new and much simpler proof of the intersection problem for Mendel-
sohn triple systems.
THE INTERSECTION PROBLEM: For each n 0 or 1(mod 3), n6= 6, determine the
set of all k such that there exists a pair of MTS(n) having exactly k cyclic triples in common.
In what follows, we will set I[n] = f0;1;2;::;x = n(n 1)3 gnfx 1;x 2;x 3;x 5g and
denote by J[n] =fkj there exists two MTS(n) having k cyclic triples in commong.
In [2] it was shown that J[3] = f2g;J[4] = f0;4g and J[n] = I[n] for all n 7 (n 0 or
1(mod 3), of course).
The objective of this thesis is a new and much simpler proof of the intersection problem
using results completely di erent from those used in the original solution.
ii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
1 Introduction and Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 The Intersection of Idempotent Quasigroups . . . . . . . . . . . . . . . . . . . . 4
3 The Basic Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1 The 3n Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 The 3n Construction: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 The 3n+ 1 Construction: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 The Solution for 3n+ 1 19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 The Solution for 3n 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
iii
Chapter 1
Introduction and Outline
The complete directed graph Dn is the graph with n vertices in which each pair of
distinct vertices are joined by two directed edges in opposite directions.
Dn=
a
b
We will denote the directed edge from a to b by (a;b). A cyclic triple is a collection of
three directed edges of the form f(a;b);(b;c);(c;a)g where a, b, and c, are distinct.a
bc
We will denote this cyclic triple by any cyclic shift of (a;b;c). Finally, a Mendelsohn
Triple System (named after N.S. Mendelsohn[3]) of order n (MTS(n)) is a pair (S;T),
where T is a collection of edge disjoint cyclic triples which partition Dn with vertex set S.
1
Example 1.1 Two MTS (7).
Let S =f1;2;3;4;5;6;7g and T1 and T2 be the following two MTS(7)s.
1
2
413 174 315 61 6 2
1
7
52
3
5 2
5
4
2
6
7
2
7
33
4
63
6
5
4
5
7
4
7
6
1
2 3
4
567
2
1 3
4
567
2
6
7
1 1 1 1 1
2
2
2 2 2
5
5
5
5
5
5
1
4
7
3
6
6
3
7
4
3 44 37
6
3 7 3
7
4
67
6
T2
T1
D7=
D7=
2
It is immediate that the two MTS(7) in this example have exactly one cyclic triple in
common, namely (2;6;7).
2
6
7
(2,6,7)=
It is well-known that the spectrum for Mendelsohn Triple Systems is precisely the set of all
n 0 or 1(mod 3) EXCEPT for n = 6 (there does not exist a Mendelsohn Triple System of
order 6), and if (S;T) is a MTS(n), jTj= n(n 1)3 .
THE INTERSECTION PROBLEM: For each n 0 or 1 (mod 3), n6= 6, determine
the set of all k such that there exists a pair of MTS(n) having exactly k cyclic triples in
common. In what follows, we will set I[n] =f0;1;2;::;x = n(n 1)3 gnfx 1;x 2;x 3;x 5g
and denote by J[n] =fkj there exists two MTS(n) having k cyclic triples in commong.
In [2] it was shown that J[3] = f2g;J[4] = f0;4g and J[n] = I[n] for all n 7 (n 0 or
1(mod 3), of course).
The objective of this thesis is a new and much more simple proof of the intersection
problem using results completely di erent from those used in the original solution.
3
Chapter 2
The Intersection of Idempotent Quasigroups
A quasigroup (Q; ) is said to be idempotent provided x x = x for all x2Q. Two
idempotent quasigroups are said to intersect in k products provided their tables agree in
exactly k cells o of the main diagonal.
Example 2.1 (Two idempotent quasigroups of order 6 intersecting in 4 products).
?1 1 2 3 4 651
23
45
6
1 6 2 5 3 44 2 5 6 1 3
2 4 3 1 6 55 3 6 4 2 1
6 1 4 3 5 23 5 1 2 4 6
?2 1 2 3 4 651
23
45
6
1 5 6 2 4 36 2 5 1 3 4
5 4 3 6 2 13 1 2 4 6 5
4 6 1 3 5 22 3 4 5 1 6
In [1] H.L. Fu proved the following theorem.
Theorem 2.1 (H.L. Fu [1]). If n 6, there exists a pair of idempotent quasigroups of order
n having k products in common if and only if k2f0;1;2;:::;x = n2 ngnfx 1;x 2;x
3;x 5g.
We will use this result to give a much simpler solution to the intersection problem
beginning with order 18.
4
Chapter 3
The Basic Constructions
We give three basic constructions in this chapter which will be used for all of the
intersection results which follow.
3.1 The 3n Construction
Let (Q; ) be an idempotent quasigroup of order n, set S = Q f1;2;3g, and de ne a
collection of cyclic triples T as follows:
1. ((a;1);(a;2);(a;3)) and ((a;1);(a;3);(a;2))2T for all a2Q; and
(a,1)
(a,2)
(a,3)
2. For each a6= b2Q the six cyclic triples ((a;i);(b;i);(a b;i + 1)), ((b;i);(a;i);(b
a;i+ 1))2T.
a b
a?b b?a a
b
(a?b) (b?a) ba
(b?a) (a?b)
5
Then, (S;T) is a MTS(3n).
3.2 The 3n Construction:
Let Q = f1;2;3;:::;3ng, = (1;2;3;:::;3n), and (Q; ) an idempotent quasigroup of
order n. Set S = Q f1;2;3g and de ne a collection of cyclic triples T as follows:
1. ((a;1);(a;2);(a ;3)) and ((a;1);(a ;3);(a;2))2T for all a2Q; and
(a,1)
(a,2)
(a?,3)
2. For each a 6= b 2 Q, the six cyclic triples ((a;1);(b;1);(a b;2)), ((b;1);(a;1);(b
a;2)), ((a;2);(b;2);((a b) ;3)), ((b;2);(a;2);((b a) ;3)), ((a;3);(b;3);((a b) 1;1)),
((b;3);(a;3);((b a) 1;1)) belong to T .
a b
a?b b?a a b
(a?b)? (b?a)? ba
(b?a)??1(a?b)??1
Then (S;T ) is a MTS(3n).
3.3 The 3n+ 1 Construction:
Let (Q; ) be an idempotent quasigroup of order n, set S =f1g[(Q f1;2;3g), and
de ne a collection of cyclic triples T as follows:
6
1. For each x2Q, place a copy of C =f(1;1;2);(1;1;3);(1;2;3);(1;2;3)g on f1g[
(fxg f1;2;3g);
?
C
(x,1)
(x,2)
(x,3)
and place these cyclic triples in T; and
2. for each a6= b2Q, place the six cyclic triples ((a;i);(b;i);(a b;i+1)), ((b;i);(a;i);(b
a;i+ 1))2T.
a b
a?b b?a a
b
(a?b) (b?a) ba
(b?a) (a?b)
Then (S;T) is a MTS(3n+ 1).
With these three constructions in hand, along with the results in Chapter 2, we can give
a very simple and elegant solution to the intersection problem for Mendelsohn triple systems
beginning with n = 18.
7
Chapter 4
The Solution for 3n+ 1 19
This is the easier of the two equivalence classes; so a good place to begin.
Let (Q; 11), (Q; 21), (Q; 12), (Q; 22), (Q; 13), (Q; 23) be any six idempotent quasi-
groups of order n 6. Further, let M1 and M2 be the two Mendelsohn triple systems of
order 4 de ned below:
M1 =f(1;2;3);(2;1;4);(1;3;4);(3;2;4)g;and
M2 =f(1;2;4);(2;1;3);(1;4;3);(2;3;4)g:
Then M1\M2 =;.
Set S =f1g[(Q f1;2;3g) and de ne two MTS(3n+ 1)s T1 and T2 as follows:
T1: (i) For each x2Q place a copy of M1 or M2 onf1g[(fxg f1;2;3g) and place
these cyclic triples in T1.
?
(x,1)
(x,2)
(x,3)
M1orM2
8
(ii) For each x6= y2Q place the six cyclic triples ((x;i);(y;i);(x 1i y;i+ 1))
and ((y;i);(x;i);(y 1i x;i+ 1)) in T1.
x y
y?11xx?11y x y
x?13y y?13x
yxx?12y y?12x
?
Then (S;T1) is a MTS(3n).
T2: (i) For each x2Q place a copy of M1 or M2 onf1g[(fxg f1;2;3g) and place
these cyclic triples in T2.
?
(x,1)
(x,2)
(x,3)
M1orM2
9
(ii) For each x6= y2Q place the six cyclic triples ((x;i);(y;i);(x 2i y;i+ 1))
and ((y;i);(x;i);(y 2i x;i+ 1)) in T2.
?
x y
x y
x yy?22x x?
22y
y?21x x?21y
x?23yy?23x
Then (S;T2) is a MTS(3n).
It is immediate that the intersection number for (S;T1) and (S;T2) isjT1\T2j= Pnj=1m+
k1 + k2 + k3, where m 2f0;4g and j(Q; 11)\(Q; 21)j = k1, j(Q; 12)\(Q; 22)j = k2,
j(Q; 13)\(Q; 23)j = k3. A straight-forward calculation shows that any k2I[3n + 1] can
be written in the form Pnj=1m + k1 + k2 + k3, where k1;k2;k3 2f0;1;2;:::;x = n2 ngn
fx 1;x 2;x 3;x 5g. Since J[3n + 1] I[3n + 1] (a necessary condition), it follows
that I[3n+ 1] J[3n+ 1] so that I[3n+ 1] = J[3n+ 1]. We have the following result.
Lemma 4.1 J[3n+ 1] = I[3n+ 1] for all 3n+ 1 19.
10
Chapter 5
The Solution for 3n 18
There are two cases to consider here: (a) k 2n, and (not too surprisingly) (b) k 2n
.
a) k 2n. We will use the 3n and 3n Constructions here. Set S = Q f1;2;3g and let
(Q; 1) and (Q; 2) be a pair of idempotent quasigroups of order n 6. Since n 6, for
anyk2f1;2;3;:::;x = n2 ngnfx 1;x 2;x 3;x 5g, we can takej(Q; 1)\(Q; 2)j= k.
It is important to note that any k 2n2f0;1;2;:::;x = n2 ngnfx 1;x 2;x 3;x 5g.
Now de ne two MTS(3n)s T1 and T2 as follows:
T1: Use the 3n Construction with (Q; 1).
a b
b?1a a?1ba b
b?1a a?1b a b
b?1a a?1b
T2: Use the 3n Construction with (Q; 2) from the rst to the second level; and (Q; 1)
between the second and third, and third and rst levels.
11
a b
b?2aa?2ba b
(b?1a)?(a?1b)?a b
(b?1a)??1 (a?1b)??1a
a
a?
Clearly the intersection number for T1\T2 is j(Q; 1)\(Q; 2)j= k.
b) k 2n. In this case we use the 3n Construction with pairs of quasigroups as in the
3n + 1 solutions. It is immediate that any k 2n2I[3n] can be written in the form
2n+k1+k2+k3 where k1;k2;k3 2f0;1;2;:::;x = n2 ngnfx 1;x 2;x 3;x 5g. Since
J[3n] I[3n], it follows that I[3n] J[3n] and I[3n] = J[3n]. We have the following
result.
Lemma 5.1 J[3n] = I[3n] for all 3n 18.
12
Chapter 6
Concluding Remarks
Combining Lemmas 4.1 and 5.1 gives the following result.
Theorem 6.1 J[n] = I[n] for all n 0 or 1 (mod 3) 18, except n = 6 for which no
MTS(6) exists.
The solution for the cases where n 16 can be found in the original paper [2] and are
handled by an eclectic collection of ad-hoc constructions. A quick glance at [2] will convince
the reader that the solution for n 18 given in this thesis is vastly superior to the original
solution in its simplicity.
13
Bibliography
[1] Hang-Lin Fu, On the construction of certain types of latin squares with prescribed
intersections, Ph. D. thesis, Auburn University, (1980).
[2] D.G. Ho man and C.C. Lindner, Mendelsohn triple systems having a prescribed number
of triples in common, Europ. J. Combinatorics, (1982), 51-61.
[3] N.S. Mendelsohn, A Natural Generalization of Steiner Triple Systems, in Computers in
Number Theory, (A.O.L. Atkin and B.J. Birch, eds), Academic Press, London, 1971,
323-328 .
14