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