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