Generalizing Clatworthy Group Divisible Designs by Julie Rogers A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 6, 2011 Keywords: Group Divisible Designs, Clatworthy Copyright 2011 by Julie Rogers Approved by Chris Rodger, C. Harry Knowles Professor of Mathematics Dean Ho man, Professor of Mathematics Curt Lindner, Distinguished University Professor of Mathematics Abstract Clatworthy described the eleven group divisible designs with three groups, block size four, and replication number at most 10. Each of these can be generalized in natural ways. In this dissertation neat constructions are provided for these new families of group divisible designs. In a previous paper the existence of one such design was settled. Here we essentially settle the existence of generalizations of eight of the remaining ten Clatworthy designs. In each case (namely, 1 = 4 and 2 = 5, 1 = 4 and 2 = 2, 1 = 8 and 2 = 4, 1 = 2 and 2 = 1, 1 = 10 and 2 = 5, 1 = 6 and 2 = 3, 1 = 3 and 2 = 1, and 1 = 6 and 2 = 2), we have proved that the necessary conditions found are also su cient for the existence of such GDD?s with block size four and three groups, with one possible exception. ii Acknowledgments First and foremost, I need to give thanks to God for the many blessings He has given me. I would also like to thank my family and friends for their never-ending love and support. Last, but de nitely not least, I need to thank my advisor, Dr. Chris Rodger, for his patience and guidance through the years. I know that I would never have reached this point without him. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Generalizing Clatworthy Design R96 . . . . . . . . . . . . . . . . . . . . . . . . 6 4 Generalizing Clatworthy Design S2 . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.1 A Corollary - Generalizing S4 . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5 Generalizing Clatworthy Design S1 . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.1 A Corollary - Generalizing S5 . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6 Generalizing Clatworthy Design S3 . . . . . . . . . . . . . . . . . . . . . . . . . 20 7 Generalizing Clatworthy Design R104 . . . . . . . . . . . . . . . . . . . . . . . . 25 8 Generalizing Clatworthy Design R105 . . . . . . . . . . . . . . . . . . . . . . . . 31 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 iv List of Figures 3.1 R96 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 R96, n = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.1 S2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 S2, n = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 S2, n = 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.1 S1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2 S1, n = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6.1 S3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.2 S3, n = 2 (Take 3 copies of each K4) . . . . . . . . . . . . . . . . . . . . . . . . 21 6.3 S3, n = 4 (The top K4 only rotates halfway horizontally on each level) . . . . . 21 7.1 R104 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.2 R104, n = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.3 R104, n = 12; the rst block of four base blocks is depicted . . . . . . . . . . . . 26 8.1 R105 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 8.2 R105, n = 6; the rst block of nine base blocks is depicted . . . . . . . . . . . . 32 8.3 R105, n = 9; the rst of seven base blocks is depicted . . . . . . . . . . . . . . . 33 v List of Tables 1.1 Clatworthy?s Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 vi Chapter 1 Introduction In this dissertation, a group divisible design GDD(n;m;k; 1; 2) is de ned to be an ordered pair (V;B), where V is a set of mn elements called symbols, together with a partition of V into m sets of size n, each element of which is called a group, and a collection B of k-subsets of V called blocks, such that each pair of symbols occurring in the same group appears together in precisely 1 blocks, while each pair of symbols occurring in di erent groups appears together in exactly 2 blocks. Symbols occuring in the same or di erent groups are known as rst or second associates respectively. A restricted version of this original de nition with 1 = 0 is more commonly used as the de nition of GDD in the milieu of combinatorial designs; in this setting, a GDD(n;m;k; 0; ) is more commonly known as a (k; )-GDD of type nm. The existence of a GDD(n;m;3; 1; 2) was completely settled by Fu, Rodger, and Sarvate [5, 6]. The most di cult and novel constructions were required when the number of groups, m, was less than k, namely when m = 2 [5]. The existence of GDDs when m>>> < >>>> : ff2i;2i+ 1g f2i;2i+ 1gji2Zn=2g if n is even ff2i 1;2ig f2i 1;2igji2(Zbn=2cnZ3)g[(Z5 Z5) if n is odd and n 17 Each element h of H(n) is a subset of Zn Zn called a hole. A HSOLS of order n and of type 2n=2 if n is even and of type 2(n 5)=251 if n is odd, on the set of symbols Zn with holes in H(n), is an n n array, L, in which: 1. Each cell (x;y) in L contains at most one symbol, containing no symbols if and only if (x;y) 2h for some h2H(n); 2. Each symbol x occurs in row y of L if and only if (x;y) =2h for all h2H(n); 3. Each symbol x occurs in column y of L if and only if (x;y) =2h for all h2H(n); and 4. For each (x;y) in no hole of H(n), there is exactly one ordered pair (k;l) such that in L, cell (k;l) contains x and cell (l;k) contains y. Throughout this dissertation we will adopt quasigroup notation by denoting the symbol in cell (i;j) of a HSOLS by i j. The set H(n) will also be routinely used. From Existence of frame SOLS of type anb1 by Xu, Zhang, and Zhu [16] (or Theorem 5.18 in [3] on page 214) we obtain the following result. 3 Theorem 2.1. Let n 6. There exists a HSOLS of order n and 1. type 2n=2 if n is even; and 2. type 2(n 5)=251 if and only if n 17 and n is odd. We also use the following design constructed by Brouwer, Schrijver, and Hanani [1] (for a more general setting see also [17] and Theorem 4.6 in [7] on page 256). Theorem 2.2. Necessary and su cient conditions for the existence of a (4; )-GDD of type mu are: 1. u 4, 2. (u 1)m 0 (mod 3), and 3. u(u 1)m2 0 (mod 12), with the exception of (m;u; )2f(2;4;1);(6;4;1)g, in which case no such GDD exists. It is also fruitful to describe these designs as graph decompositions, each symbol being represented by a vertex. Let G(n;3; 1; 2) be the graph with vertex set Zn Z3 in which (u;i) is joined to (v;j) with 1. 1 edges if i = j, and 2. 2 edges if i6= j. Then a GDD(n;3;4; 1; 2) is clearly equivalent to a partition of the edges of G(n;3; 1; 2) into sets of size 6, each of which induces a copy of K4; for each i2Z3, Zn fig is a group. These two notions will be used interchangeably throughout this dissertation. To complete these designs we must rst de ne the nesting of a GDD. A nesting of a GDD(V;P;B) with associated graph G(n;3; 1; 2) is de ned to be a function of f : B!V 4 such that ffx;f(b)gjx2b2Bg= E(G(n;3; 1; 2)). More informally, a GDD with block size 3 is said to be nested if a fourth point can be added to each block such that the edges gained from the nesting cover precisely the same edges as the original GDD. So each pair fu;vgof vertices occurs together in twice as many blocks of size 4 in the nested design as the number of triples containingfu;vgin the original GDD. We will use the following theorem provided by Jin Hua Wang [15]. Theorem 2.3. There exists a nesting of a GDD(t;n;3; 1 = 0; 2 = ) if and only if t(n 1) 0 (mod 6) and n 4. 5 Chapter 3 Generalizing Clatworthy Design R96 In this chapter we generalize R96-designs (see Figure 3.1), completely settling their existence. For completeness, we present a cyclic construction for the smallest R96-design. Figure 3.1: R96 Lemma 3.0.1. There exists a GDD(2;3;4; 4;5). Proof. (Z6;B) with B =ffi;i+1;i+3;i+5g;fi;i+1;i+2;i+5gji2Z6gis such a design, where the groups are (i;i+ 3) for each i2Z3. (See Figure 3.2.) We now use this small R96-design to obtain the following result. Theorem 3.1. There exists a GDD(n;3;4; 4;5) if and only if n 2 (mod 6). Proof. We start by proving the necessity, so suppose there exists a GDD(n;3;4; 4;5). Let us begin by looking at the number of blocks. Since each block contains six edges, the number of blocks in any such design is 6 Figure 3.2: R96, n = 3 b = jE(G(n;3; 4;5))j6 = 3( 4n(n 1) 2 + 5n 2) 6 = 7n2 2n 2 : Clearly the number of blocks is an integer, so n must be even. Each time a vertex (u;i) is used in a block, 3 of its incident edges are used. So the number of blocks containing (u;i) is dG(n;3;4;5)(u;i) = 4(n 1) + 10n3 = 143 n 43; which also must be an integer. So n 2 (mod 3). So n 2 (mod 6) is a necessary condition. Next we prove the su ciency, so suppose that n 2 (mod 6). We will show there exists a GDD(n;3;4; 4;5), (Zn Z3;B) with groups Zn flg for each l2Z3. Since Lemma 3.0.1 produces a GDD(2;3;4; 4;5), we can assume that n 8. The design will be described as a graph decomposition of the graph G(n;3; 4;5). For each i2Zn=2 let B(i) be a copy of R96 on the vertices in C(i) =f2i;2i+ 1g Z3, where for each l 2 Z3, f2i;2i + 1g flg is a group. Since n 8 > 6, by Theorem 2.1 we can let S be a HSOLS of order n and of type 2n=2 on the set of symbols, Zn with holes in H(n). By Theorem 2.2 (since n 8 and u = n=2 4), for each l 2 Z3 let 7 B0(l) be a copy of a (4;2)-GDD of type 2n=2 on the vertex set Zn flg with groups in H0(l) =ff2i;2i+ 1g flgji2Zn=2g. Then de ne the blocks in the design as follows: B = (Si2Zn=2 B(i)) [ (Sl2Z3 B0(l)) [ff(i;a);(j;a);(i j;a+ 1);(j i;a+ 2)gj0 i;j 6, by Theorem 2.1 we can let S be a HSOLS of order n and of type 2n=2 on the set of symbols, Zn, with holes in H(n). By Theorem 2.2 (since n 8 and u = n=2 4), for each l 2 Z3 let B0(l) be a copy of a (4;2)-GDD of type 2n=2 on the vertex set Zn flg with groups in H0(l) =ff2i;2i+ 1g flgji2Zn=2g. Then de ne the blocks in the design as follows: B = (Si2Zn=2 B(i)) [ (Sl2Z3 B0(l)) [ff(i;a);(j;a);(i j;a+ 1);(j i;a+ 1)gj0 i 6, by Theorem 2.1 we can let S be a HSOLS of order n and of type 2(n 5)=251 on the set of symbols Zn, with holes in H(n). By Theorem 2.2 (since n 17 and u = (n 5)=2 6 > 4), for each l2Z3 let B0(l) be a copy of a (4;2)-GDD of type 2(n 5)=251 on the vertex set Zn flg with groups in H0(l) = fff2i 1;2ig flgji2 Zbn=2cnZ3g[(Z5 flg)g. Then de ne the blocks in the design as follows: B = (Si2(Zbn=2cnZ2)B(i)) [ (Sl2Z3 B0(l)) [ff(i;a);(j;a);(i j;a+ 1);(j i;a+ 1)gj0 i