ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.52790 J. Algebra Comb. Discrete Appl. 3(3) • 135–144 Received: 23 October 2015 Accepted: 17 February 2016 Journal of Algebra Combinatorics Discrete Structures and Applications The 3-GDDs of type g3u2 Research Article Charles J. Colbourn, Melissa S. Keranen, Donald L. Kreher Abstract: A 3-gdd of type g3u2 exists if and only if g and u have the same parity, 3 divides u and u ≤ 3g. Such a 3-gdd of type g3u2 is equivalent to an edge decomposition of Kg,g,g,u,u into triangles. 2010 MSC: 05B05, 05B07, 05C70 Keywords: Group divisible designs, Partial triple systems, Graph decomposition 1. Introduction A group divisible design (gdd) is a decomposition of the complete multipartite graph into complete subgraphs. The complete subgraphs used are the blocks of the gdd and are presented by giving the subset of the vertices they span. The partite sets are groups. Formally a K -gdd is a triple (V, B, G ) where 1. V is a finite set of points; 2. B is a collection of subsets of V , where |B| ∈ K , for all B ∈ B; 3. G is a partition of V into groups. 4. Every pair of points is in exactly one block or group. The type of a gdd is the multiset of its group sizes. Thus a decomposition of Kg0,g1,g2,...,gt−1 into complete subgraphs is a gdd of type {g0,g1,g2, . . . ,gt−1}. If the gdd has ti groups of size gi it is our custom to specify the type with the notation: gt00 g t1 1 g t2 2 · · ·g t` ` . Also if K = {k} we write k-gdd instead of {k}-gdd. The blocks of a 3-gdd are usually called triples or triangles. For example a 3-gdd of type 4321 is a decomposition of K4,4,4,2 into triangles. Charles J. Colbourn; School of CIDSE, Arizona State University, Tempe, Arizona 85287-8809, U.S.A. (email: charles.colbourn@asu.edu). Melissa S. Keranen, Donald L. Kreher (Corresponding Author); Department of Mathematical Sciences, Michigan Technological University, Houghton, Michigan 49931-1295, U.S.A. (email: msjukuri@mtu.edu, kreher@mtu.edu). 135 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 Theorem 1.1. For a 3-gdd of type g1g2 · · ·gs with g1 ≥ ··· ≥ gs ≥ 1, s ≥ 2, and v = ∑s i=1 gi to exist, necessary conditions include (Colbourn [2]): 1. ( v 2 ) ≡ ∑s i=1 ( gi 2 ) (mod 3); 2. gi ≡ v (mod 2) for 1 ≤ i ≤ s; 3. g1 ≤ ∑s i=3 gi; 4. whenever αi ∈{0,1} for 1 ≤ i ≤ s and v0 = ∑s i=1 αigi, v0(v −v0) ≤ 2 [( v0 2 ) + ( v −v0 2 ) − s∑ i=1 ( gi 2 )] 5. 2g2g3 ≥ g1[g2 + g3 − ∑s i=4 gi]; and 6. if g1 = ∑s i=3 gi then 2g3g4 ≥ (g1 −g2)[g3 + g4 − ∑s i=5 gi]. These conditions are known to be sufficient when 1. (Wilson [8, 9]) g1 = · · · = gs; 2. (Colbourn, Hoffman, and Rees [5]) g1 = · · · = gs−1 or g2 = · · · = gs; 3. (Colbourn, Cusack, and Kreher [3]) 1 ≤ t ≤ s, g1 = · · · = gt, and gt+1 = · · · = gs = 1; 4. (Bryant and Horsley [1]) g3 = · · · = gs = 1; and 5. (Colbourn [2]) ∑s i=1 gi ≤ 60. Surprisingly, in no other cases are necessary and sufficient conditions known for any other class of 3-gdds (of index 1). Partial results are known when g3 = · · · = gs = 2 [6]. Theorem 1.1 establishes that no 3-gdd with two groups exists; every 3-gdd with three groups has g1 = g2 = g3; and every 3-gdd with four groups has type g4 or g3u1; moreover, the first and second sufficient conditions ensure that all such 3-gdds exist. Turning to five groups, the situation is much less satisfactory. While Theorem 1.1 handles all types g5, g4u1, and g1 · · ·g5 with ∑5 i=1 gi ≤ 60, many more cases are possible. Indeed it may happen that a 3-gdd with five groups has all groups of different sizes; for example, a 3-gdd of type 171111917151 exists [2]. Hence the general existence problem for five groups appears to be substantially more complicated than cases with fewer groups. We address one part of this problem, when there are only two group sizes. The focus of this article is to prove Theorem 1.2 (Main Theorem). A 3-gdd of type g3u2 exists if and only if g ≡ u (mod 2), u ≡ 0 (mod 3), and u ≤ 3g. If a 3-gdd of type g3u2 exist, then v = 3g + 2u ≡ 2u (mod 3) and v ≡ g (mod 3). Thus it follows from Theorem 1.1 conditions (1) and (2) that g ≡ u (mod 2) and u ≡ 0 (mod 3). Condition 3 of Theorem 1.1 is exactly the necessary conditions for the existence of a 3-gdd of type g3u2 are established by Theorem 1.1. Sufficiency is proved in the sections that follow. 2. 3-GDDs of type g3u2 Let γij` be the number of triples that contain points of groups Gi, Gj, and G`. Elementary counting establishes that when |G1| = |G2| = |G3| = g and |G4| = |G5| = u, we have γ123 = g2 − 13(u(3g − u)), γ124 = γ125 = γ134 = γ135 = γ234 = γ235 = 1 6 (u(3g − u)), and γ145 = γ245 = γ345 = 13u 2. An easy case arises when u = 3g: 136 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 Lemma 2.1. There exists a 3-gdd of type g3(3g)2, for all g. Proof. A 3-gdd of type (3g)3 exists. Partition one of the groups into three groups of size g on these groups place the triples of a 3-gdd of type g3. A one-factor on a set S is a set of |S|/2 vertex-disjoint edges. A holey one-factor on a set S with hole H is a set of (|S|− |H|)/2 vertex-disjoint edges in which no edge is incident to a vertex in H. We use the following result. Lemma 2.2. (Rees [7]) Let h ≥ 1 and 0 ≤ r ≤ 2h, (h,r) 6∈ {(1,2),(3,6)}. There exists a {2,3}-gdd of type (2h)3 which is resolvable into r parallel classes of blocks of size 3 and 4h− 2r parallel classes of blocks of size 2. Consequently whenever 0 ≤ x ≤ r, the edges of K2h,2h,2h can be partitioned into 4h−2r one-factors, 3x holey one-factors (x for each group), and r −x parallel classes of triples. Theorem 2.3. If there exists a 3-gdd of type x3u2 with g ≡ x (mod 2) and g ≥ 2x+u, then there exists a 3-gdd of type g3u2. Proof. Write h = g−x 2 . Without loss of generality, u 6= 0 so u ≥ 3. Because g ≥ 2x + u, then h ≥ x+u 2 ≥ 2. When h = 3, we have (g,x,u) ∈ {(7,1,3),(9,3,3)}, and the required gdds are from Theorem 1.1. Henceforth h 6∈ {1,3}. Choose groups {Gi : 1 ≤ i ≤ 5} with |G1| = |G2| = |G3| = g and |G4| = |G5| = u. For i ∈ {1,2,3} partition Gi into parts Gi,1 and Gi,2 where |Gi,1| = x and |Gi,2| = g − x = 2h. Place a 3-gdd of type x3u2 aligning the groups on G1,1, G2,1, G3,1, G4, and G5. Now r = 2h−u = g −x−u ≥ 2x + u−x−u = x. So use Lemma 2.2 with groups G1,2, G2,2, G3,2 to construct a partition of K2h,2h,2h into 4h− 2r one-factors {Fy : y ∈ G4 ∪G5}; for i ∈ {1,2,3}, x holey one-factors {Hi,x : x ∈ Gi,1} missing Gi,2; and r − x parallel classes of triples. Include all (2h)(r − x) triples in the r − x parallel classes. Then for each y ∈ G4 ∪ G5, adjoin y to each edge in Fy, forming 2u(3(2h)) triples. Finally, for i ∈{1,2,3} and x ∈ Gi,1, adjoin point x to each edge in Hi,x to form 6xh additional triples. Corollary 2.4. There exists a 3-gdd of type g3u2, whenever g ≥ 5 3 u, u ≡ 0 (mod 3), and g ≡ u (mod 2). Proof. Apply Theorem 2.3 with x = u/3. In the remainder, the expression give weight w to the point x means to replace x with a set of w new points x1,x2, . . . ,xw; and if S = {s1,s2, . . . ,sk} is a set of points given weights (w(si) : 1 ≤ i ≤ k), then to place a 3-gdd of type {w(s1),w(s2), . . . ,w(sk)} on S means to include all triples in a 3-gdd of type {w(s1),w(s2), . . . ,w(sk)} with groups {{si,1,si,2,si,3, . . . ,si,w(si)} : 1 ≤ i ≤ k}. A synonymous expression is to fill the inflated block with a 3-gdd of type {w(s1),w(s2), . . . ,w(sk)}. This is illustrated in the following. Lemma 2.5. If a 3-gdd of type (g/w)3(u/w)2 exists, then a 3-gdd of type g3u2 also exists. Proof. Starting with a 3-gdd of type (g/w)3(u/w)2, give weight w to the points using a 3-gdd of type w3, which always exists. Recall that a 5-gdd of type k5 is equivalent to 3 mutually orthogonal Latin squares of order k, which are known to exist when k 6∈ {2,3,6,10} [4]. (When k = 10 existence remains uncertain, but they do not exist for k ∈{2,3,6}.) Lemma 2.6. If there exists a 5-gdd of type k5, and integers g,u with g ≡ u ≡ k (mod 2), 3k ≤ g,u ≤ 9k, and u ≡ 0 (mod 3), then there exists a 3-gdd of type g3u2. 137 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 Proof. Form a 5-gdd of type k5 with groups G1,G2,G3,G4,G5. Let the points of Gi be {xi1, . . . ,xik}, so that {x1k,x2k,x3k,x4k,x5k} is a block. Write g = 3a + 9(k−1−a) + b with 0 ≤ a ≤ k−1 and b ∈{3,5,7,9}. Write u = 3c + 9(k−c) with 0 ≤ c ≤ k. Set w(xij) =   b if 1 ≤ i ≤ 3 and j = k, 3 if 1 ≤ i ≤ 3 and 1 ≤ j ≤ a, 3 if 4 ≤ i ≤ 5 and 1 ≤ j ≤ c, 9 if 1 ≤ i ≤ 3 and a + 1 ≤ j < k, 9 if 4 ≤ i ≤ 5 and c + 1 ≤ j ≤ k. According to [2], there exist 3-gdds of types 35, 5134, 7134, 9134, 915133, 5332, 917133, 7332, 9233, 925132, 927132, 9332, 9253, 935131, 937131, 9273, 9431, 9451, 9471, and 95. Each block of the 5-gdd of type k5 has weights forming one of these types, so we place a 3-gdd on the points arising from each. Theorem 2.7. Suppose u ≡ 0 (mod 3), u ≡ g (mod 2) and 3 ≤ u ≤ 3g. Then a 3-gdd of type g3u2 exists, except possibly when 3g + 2u > 60 and g ∈{9,10,11,13,18,20,22,30,32,34} and 3 5 g < u < 3g; or (1) g ≡ 1 (mod 3) and u = 3g −6; or (2) u ∈{18,30} and u < g < 5 3 u. (3) Proof. Using Lemma 2.1 and Corollary 2.4, assume that 3 5 g < u < 3g. Write u = 3` and g = 3m + r, where r ∈ {0,1,2}; then ` ≡ m (mod 2) if and only if r ∈ {0,2}. To handle cases with u ≥ g and g 6∈ S = {2,4,6,8,9,10,11,13,18,20,22,30,32,34}, apply Lemma 2.6 with k = m when r ∈ {0,2} and k = m− 1 when r = 1. When applied with k = m− 1, u ≤ 9m− 9, leading to the possible exceptions in (2). When g ∈ {2,4,6,8} and u < 3g, all required gdds are from [2]. Thus when u ≥ g, the possible exceptions are listed in (1) and (2). To handle cases when u ≤ g and u 6∈ T = {6,9,18,30}, apply Lemma 2.6 with k = `. When u ∈{6,9} and u ≤ g ≤ 5 3 u, all required gdds are from [2]. Thus when u ≤ g, the possible exceptions are listed in (3). Lemma 2.8. There exists a 3-gdd of type 133152. Proof. Begin with a 5-gdd of type 55. Fix a block B and give weights 1,1,1,3,3 to it. On the remaining points give weight 3. Fill the inflated blocks with 3-gdds of type 1331, 1134, 35 from [2]. Theorem 2.9. A 3-gdd of type g3u2 exists if and only if g ≡ u (mod 2) and u ≡ 0 (mod 3) except possibly when g ≡ 1 (mod 3), g ≥ 16, and u = 3g −6; or g3u2 ∈   93212, 103242, 113152, 113212, 113272, 133212, 133272, 133332, 183422, 183482, 203422, 203482, 203542, 223422, 223482, 223542, 223602, 303842, 323782, 323902, 343842, 343962.   Proof. Apply Lemma 2.1, Lemma 2.5, Theorem 2.3, and Theorem 2.7. Then apply Lemma 2.6 with k = 4 to handle types 183u1 for u ∈ {12,24} and 223u1 for u ∈ {24,30,36}; and with k = 8 to handle 303u1 for u ∈ {24,48,72}, 323u1 for u ∈ {30,42,54,66}, and 343u1 for u ∈ {24,36,48,60,72}. Apply Lemma 2.8 to handle 133152. 138 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 3. Incomplete group divisible designs Let K be a set of positive integers, each at least 2. An incomplete group divisible design (K-igdd) of type (g1 : h1)u1 · · ·(gs : hs)us is a quadruple (V, B, G ,H) where 1. V is a set of ∑s i=1 uigi elements; 2. H ⊂ V , the hole, contains ∑s i=1 uihi elements; 3. G = {G1, . . . ,Gm} is a partition of V into m = ∑s i=1 ui groups G1, . . .Gm so that ui of the groups have size gi and contain hi points of H, for 1 ≤ i ≤ s; 4. B is a set of blocks with |B| ∈ K whenever B ∈ B, so that every pair of elements that are in the hole or in a group do not appear in a block, and every other pair occurs in exactly one block. When K = {k}, we write k-igdd. Lemma 3.1. Suppose that K is a set of odd positive integers. If a K-igdd of type (g1 : h1)u1 · · ·(gs : hs)us exists and w ≥ 2, then a 3-igdd of type (wg1 : wh1)u1 · · ·(wgs : whs)us exists. Proof. Give weight w to each point and fill with a 3-gdd of type wk for k ∈ K. Corollary 3.2. A 3-igdd of type (12 : 3)1(6 : 3)4 exists. Proof. A {3,5}-igdd of type (4 : 1)1(2 : 1)4 exists with groups {{di,xi} : 0 ≤ i ≤ 3}∪{y,z1,z2,z3}, hole {d0,d1,d2,d3,y}, and blocks {{di,x(i+j) mod 4,zj} : 0 ≤ i ≤ 3,1 ≤ j ≤ 3} and {x0,x1,x2,x3,y}. Apply Lemma 3.1 with w = 3. Lemma 3.3. If a 3-igdd of type (3g : 3h)3 and a 3-igdd of type (g : h)3 exist, then a 3-igdd of type (3g : 3h)2(g : h)3 exists. Proof. Fill one group of the 3-igdd of type (3g : 3h)3 with the 3-igdd of type (g : h)3. Corollary 3.4. When 1 ≤ h ≤ 1 2 g, a 3-igdd of type (3g : 3h)2(g : h)3 exists. In particular, a 3-igdd of type (6 : 3)2(2 : 1)3 and a 3-igdd of type (12 : 3)2(4 : 1)3 exist. Proof. A 3-igdd of type (g : h)3 is equivalent to a latin square of side g with a subsquare of side h, which exist whenever 1 ≤ h ≤ 1 2 g, [4]. Lemma 3.5. A 3-igdd of type (4 : 1)i(2 : 1)5−i exists when i ∈ {0,2}. Hence a 3-igdd of type (6 : 3)5 and a 3-igdd of type (12 : 3)2(6 : 3)3 exist. Proof. When i = 0, form blocks {{ai, i + 1, i + 4},{ai, i + 2, i + 3} : i ∈ Z5} with groups {ai, i} and hole {ai : i ∈ Z5}. When i = 2, a solution follows: Blocks: {5,7,10}, {5,6,11}, {4,9,10}, {4,8,12}, {4,7,13}, {3,8,10}, {3,6,12}, {3,4,11}, {2,9,12}, {2,7,11}, {2,6,13}, {2,5,8}, {1,8,11}, {1,7,12}, {1,4,6}, {1,2,10}, {0,9,11}, {0,8,13}, {0,6,10}, {0,5,12}, {0,3,7}, {0,2,4}. Groups: {0,1}, {2,3}, {4,5}, {6,7,8,9}, {10,11,12,13}. Hole: {1,3,5,9,13}. Use Lemma 3.1 with weight 3 to obtain the specific igdds. 139 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 Lemma 3.6. There exist 3-igdds of type (4 : 1)3(6 : 3)i(12 : 3)2−i for i ∈{0,1,2}. Proof. When i = 0, apply Corollary 3.4. When i = 2, start with points {xj : x ∈ Z5, j ∈ Z3}; elements with the same x-coordinate are in the same group of the igdd. Place orbits of triples {00,10,20}, {00,30,40}, {10,30,41}, and {20,30,42}, developing the subscript modulo 3. Then the remaining pairs {xi,yj} with x 6= y can be partitioned into a holey 1-factor missing {x0,x1,x2} for x ∈{0,1,2} and three holey 1-factors missing {x0,x1,x2} for x ∈{3,4}. Extending these 9 holey 1-factors gives the 9 points in the hole of the igdd. To construct a 3-igdd of type (4 : 1)3(6 : 3)1(12 : 3)1 first form seven sets of size 3: {Ai = {aij : j ∈ Z3} : i ∈ Z3}, B = {bj : j ∈ Z3}, and {Ci = {cij : j ∈ Z3} : i ∈ Z3}. Let H = {αi,βi,γi : i ∈ Z3} be 9 additional points. We construct the 3-igdd with groups:( A0 ∪{α0} ) , ( A1 ∪{α1} ) , ( A2 ∪{α2} ) , ( B ∪{β0,β1,β2} ) , ( C0 ∪C1 ∪C2 ∪{γ0,γ1,γ2} ) and hole H. Now form 1. the triples of a 3-gdd of type 33 on groups {β0,β1,β2}, Ai, and Ci for i ∈ Z3, 2. {{γi,bj,aij},{γi,a i+1 j ,a i+2 j } : i,j ∈ Z3}, 3. {{αi,ai+1j ,c i+2 j },{αi,a i+2 j ,c i+1 j },{αi,bj,c i j} : i,j ∈ Z3}, 4. {{bj,aij+1,c i+1 j+2},{bj,a i+1 j+2,c i j+1} : i,j ∈ Z3}, 5. {{aij,c i+1 j+2,a i+2 j+1} : i,j ∈ Z3}, 6. {{a0j,a 1 j+1,a 2 j+2} : j ∈ Z3}. It is an easy but tedious exercise to verify that these triples provide the desired igdd. Lemma 3.7. A 3-igdd of type (5 : 1)3(9 : 3)2 exists. Proof. Form a set X = Z3 × Z4 × Z2 of points. Let Gi = {i} × {0,1} × Z2 for i ∈ Z3, and let Gj+1 = Z3×{j}×Z2 for j ∈{2,3}. On X with groups {Gi : 0 ≤ i ≤ 4} we construct a partition of pairs not in a group into one holey parallel class of ten pairs missing Gi for each i ∈ {0,1,2}; three parallel clases of nine pairs missing Gi for each i ∈ {3,4}; and 48 triples. Once constructed, extending holey parallel classes produces the desired igdd. First we make the triples. Form a 3-gdd of type 43 on Z3 ×Z4 having a parallel class on {Z3 ×{j} : j ∈ Z4} and groups on {{i}×Z4 : i ∈ Z3}. This has 12 triples; give weight 2 to form 48 triples. For i ∈ Z3 let Fi =   {(i,2,0),(i,3,0)}, {(i,2,1),(i,3,1)}, {(i + 1,2,0),(i + 1,3,1)},{(i + 1,0,0),(i + 1,2,1)},{(i + 1,1,1),(i + 1,3,0)}, {(i + 2,2,1),(i + 2,3,0)},{(i + 2,0,1),(i + 2,2,0)},{(i + 2,1,0),(i + 2,3,1)}, {(i + 1,0,1),(i + 2,0,0)},{(i + 1,1,0),(i + 2,1,1)}.   Then Fi is a holey parallel class for Gi for i ∈ Z3. For i ∈ Z3 and σ ∈ Z2 let σ = 1−σ and let Hiσ =   {(i + 1,σ,σ),(i + 2,σ,σ)},{(i,σ,σ),(i + 1,σ,σ)}, {(i,σ,σ),(i + 2,σ,σ)}, {(i,σ,σ),(i,2 + σ,σ)}, {(i + 1,σ,σ),(i + 1,2 + σ,σ)}, {(i + 2,σ,σ),(i + 2,2 + σ,σ)}, {(i,σ,σ),(i,2 + σ,σ)}, {(i + 1,σ,σ),(i + 1,2 + σ,σ)},{(i + 2,σ,σ),(i + 2,2 + σ,σ)}.   Then {Hiσ : i ∈ Z3} contains three holey parallel classes for G3+σ for σ ∈ Z2. 140 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 4. Using incomplete group divisible designs Theorem 4.1. Let m,k be integers. If 5 ≤ m ≤ k ≤ 3m, m ≡ k (mod 2), and m 6∈ {6,10}, then there exist 3-gdds of type (3m + 1)3(3k + 3)2 and (3m + 3)3(3k + 3)2. Proof. There exists a 5-gdd of type m5 that has a parallel class P of blocks (this is equivalent to three idempotent MOLS of side m, see [4]). Let G1,G2,G3,G4,G5 be its groups. Give weight 3 to all points in G1 ∪G2 ∪G3. In each of 3m−k2 of the blocks of P give weight 3 to the two points of the block in G4 or G5; for the remaining k−m2 of the blocks of P , give weight 9. Add a set H of 15 or 9 points distributed 3,3,3,3,3 or 1,1,1,3,3 to the groups to obtain group types (3m + 3)3(3k + 3)2 and (3m + 1)3(3k + 3)2 respectively. Fill blocks not in the parallel class P with a 3-gdd of type 9i35−i, i = 0,1 or 2 from [2]. Fill blocks that are in the parallel class P with a 3-igdd of type (6 : 3)5 and a 3-igdd of type (6 : 3)3(12 : 3)2, or a 3-igdd of type (4 : 1)3(6 : 3)2 and a 3-igdd of type (4 : 1)3(12 : 3)2, all having hole H. Fill H with a 3-gdd of type 35 or a 3-gdd of type 1332 respectively. Corollary 4.2. There exist 3-gdds with g ≡ 1 (mod 3), g ≥ 16, g 6∈ {19,31}, and u = 3g−6; and when g3u2 ∈ { 183422,183482,223422,223482,223542,223602,303842,343842,343962 } . Proof. Apply the first statement of Theorem 4.1 with (m,k) = (g−1 3 ,g − 3) when g ≡ 1 (mod 3), g ≥ 16, g 6∈ {19,31} and u = 3g − 6. Apply the first statement with m = 7 and k ∈ {13,15,17,19} to treat the cases with g = 22; and with m = 11 and k ∈{27,31} to treat the cases with g = 34. Apply the second statement with m = 5 and k ∈{13,15} to handle the cases with g = 18, and with (m,k) = (9,27) to handle 303842. It remains to treat g3u2 ∈ { 93212, 103242, 113152, 113212, 113272, 133212, 133272, 133332, 193512, 203422, 203482, 203542, 313872, 323782, 323902. } Next we extend Theorem 4.1: Theorem 4.3. Let m ≥ 5 be an integer with m 6∈ {6,10,14,18,22}. Let k ≡ m (mod 2) be an integer, where m ≤ k ≤ 3m. Let α be an integer with 1 ≤ α ≤ m, and let a be an integer for which α ≤ a ≤ 3α and a ≡ α (mod 2). Then a 3-igdd of type ((3m + a : a)3(3k + 3α : 3α)2 exists. If in addition a 3-gdd of type a3(3α)2 exists, then a 3-gdd of type (3m + a)3(3k + 3α)2 exists. Proof. There are 4 MOLS of order m [4] and hence there exists a 5-gdd of type m5 with α disjoint parallel classes {Pi : 1 ≤ i ≤ α}. Let G1,G2,G3,G4,G5 be its groups. Give weight 3 to all the points in G1 ∪G2 ∪G3. In each of G4 and G5 give weight 3 to 3m−k2 of the points and weight 9 to the remaining k−m 2 points. Now for 1 ≤ i ≤ α, let Hi contain three new points in each of G4 and G5; and either three or one new points in each of G1,G2,G3 according to whether i ≤ a−α2 or not. Fill blocks not in ⋃α i=1 Pα using a 3-gdd of type 9 i35−i with i ∈{0,1,2}. For each parallel class Pi, fill each block with an igdd of type (6 : 3)3(12 : 3)2, (6 : 3)4(12 : 3)1, or (6 : 3)5, that has hole Hi; these are from Corollary 3.2 and Lemma 3.5. This produces the 3-igdd of type ((3m + a : a)3(3k + 3α : 3α)2. If a 3-gdd of type a3(3α)2 exists, use it to fill the hole. Corollary 4.4. There exist 3-gdds of types 193512, 203u2 for u ∈ {42,48,54}, 313872, and 323u2 for u ∈{78,90}. Proof. Theorem 4.3 handles 193512 using (m,α,a) = (5,2,4) and k = 15; 203u2 for u ∈ {42,48,54} using (m,α,a) = (5,3,5)and k ∈{11,13,15}; 313872 using (m,α,a) = (9,2,4) and k = 27; and 323u2 for u ∈{78,90} using (m,α,a) = (9,3,5) and k ∈{23,27}. 141 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 It remains only to treat a few cases with g ≤ 13. A variant of Theorem 4.3 uses a different weighting: Theorem 4.5. Let m ≥ 5 be an integer with m 6∈ {6,10,14,18,22}. Let α be an integer with 1 ≤ α ≤ m, and let a be an integer for which α ≤ a ≤ 3α and a ≡ α (mod 2). Then a 3-igdd of type ((m + α : α)3(3m + a : a)2 exists. If in addition a 3-gdd of type α3a2 exists, then a 3-gdd of type ((m + α)3(3m + a)2 exists. Proof. Let G1,G2,G3,G4,G5 be the groups of a 5-gdd of type m5 with α disjoint parallel classes {Pi : 1 ≤ i ≤ α}. Give weight 1 to all points in G1 ∪G2 ∪G3, and weight 3 to all points in G4 ∪G5. Fill blocks not in ⋃α i=1 Pα using a 3-gdd of type 1 332. For 1 ≤ i ≤ α, let Hi contain three new points in each of G1,G2,G3; and either three or one new points in each of G4 and G5 according to whether i ≤ a−α2 or not. For 1 ≤ i ≤ a−α 2 , fill each block of Pi with an 3-igdd of type (2 : 1)3(6 : 3)2 that has hole Hi. For a−α2 < i ≤ α, fill each block of Pi with an 3-igdd of type (2 : 1)3(4 : 1)2 that has hole Hi. This produces the 3-igdd of type ((m + α : α)3(3k + a : a)2. Corollary 4.6. There exist 3-gdds of types 93212, 103242, 113272, 133272, and 133332. Proof. Apply Theorem 4.5 with (m,α,a) = (5,4,6) to handle 93212; (m,α,a) = (7,3,3) to handle 103242; (m,α,a) = (7,4,6) to handle 113272; (m,α,a) = (7,6,6) to handle 133272; and (m,α,a) = (9,4,6) to handle 133332. Theorem 4.7. If there exist 3-gdds of types g3u2 and a3b2 and a 3-igdd of type (g+a : a)3(u+b : b)2, then for all w ≥ 3 there also exists a 3-gdd of type (wg + a)3(wu + b)2. Proof. Let {Gi : 1 ≤ i ≤ 5} be groups of size g,g,g,u,u respectively and set G = ⋃5 i=1 Gi. Let {Hi : 1 ≤ i ≤ 5} be groups of size a,a,a,b,b respectively and set H = ⋃5 i=1 Hi. If x ∈ G , then we denote by x, the w-element set x = x×Zw and set Gi = ⋃ x∈Gi x. We construct the 3-gdd of type (wg +a) 3(wu+b)2 on groups {(Gi ∪Hi) : 1 ≤ i ≤ 5}. If x,y,z ∈ G , let P(x,y,z) = { {x×{i},y ×{i},z ×{i}} : i ∈ Zw } ; this is a parallel class of triples. Because w ≥ 3 there is an idempotent latin square of side w; consequently a 3-gdd of type w3 can be constructed with groups x,y,z that contains the parallel class P(x,y,z). Let D(x,y,z) be the triples in this gdd that are not in P(x,y,z). Let A be a 3-igdd of type (g + a : a)3(u + b : b)2 on the groups (Gi ∪Hi), i = 1,2,3,4,5 and hole H . Let B be a 3-gdd of type g3u2 on the groups Gi, i = 1,2,3,4,5. To construct the 3-gdd of type (wg + a)3(wu + b)2 we take the triples in: {{h,x ×{i},y ×{i}} : i ∈ Zw} whenever { h,x,y } is a triple in A intersecting the hole H in the point h; P(x,y,z) whenever{ x,y,z } is a triple in A disjoint from the hole H ; D(x,y,z) whenever { x,y,z } is a triple in B; and a 3-gdd of type a3b2 on the hole H . Corollary 4.8. There exists a 3-gdd of type 133212. Proof. There exist 3-gdds of types 4362 and 1332 and a 3-igdd of type (5 : 1)3(9 : 3)2 from Lemma 3.7. Apply Theorem 4.7 with w = 3. Theorem 4.9. If there exist 3-gdds of types g3u2 and a3b2 and a 3-igdd of type (g +a : a)3(u+b : b)2, then for all w ≥ 3 there also exists a 3-gdd of type (wg + (w −1)a)3(wu + (w −1)b)2. 142 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 AP BS CR EV FW HM IO KU gG hL io jq kD lN mJ nT pQ rX BU CO DV ER FQ HT JS LM gm ho iN jI kW lK nG pX qP rA AM BW CN DX GV HQ IT KR gU hm iE jF kn lO oP pL qS rJ AU CM DQ GN HR JW KO LS gV hT iq jE kP lm nX oF pB rI AS BV CW EQ IX JN gM hD iL jO kF lT mK nP oR pG qH rU AT EP HS IU KX LO aG bC cD dB eW fJ mQ nF oV pM qN rR AW BX EM FN GQ IR KP aS bH cO dU eD fp mT nL oC qJ rV AO BM DW FR GP HX JV LU aE br cq dQ eC fT mI nN oS pK CV DT FM HU IW JR LQ ap bP cX dN eA fO mS nK oE qB rG DN ET FU GM JP KW LX aQ bV cm dI eB fS nH oA pO qR rC AX BQ DO FV IS KM LW ag bE cG dP eR fC hN iU jT kH lJ AN BT CP DS EW FO GU IV JX KQ aL bM cl dg ei fk hR jH AR BO CU DM FS GT HV IN LP ai bk cW dJ eX fl gQ hE jK BP CT DR EU GS HN JO KV aX bW ci dh eQ fA gI jM kL lF DP EN FX GO HW JQ KT LV aI bh cA dC ej fU gB iM kR lS aB bJ ck dp eL fD gK hI iA jm lE nC oH qG rF ao bL cp di eI fH gA hG jB kK lC mE nJ qF rD an bF cE dr eK fg hA iB jG kC lH mL oJ pI qD aF bB cC dm eG fL gJ hr iK jn kI lA oD pH qE aD bl cF dL eE fj gn hB iC kA mG oK pJ qI rH al bo cJ dH eg fI hF iD jA kG mC nB pE qK rL am bG cL dK en fE gF hH iI jJ ko lD pA qC rB aC bA cB dF eH fK gD hJ im jo kp lG nI qL rE aJ bI cK dE eo fG gC hq iH jL kB lr mA nD pF aV bQ cM dn el fW gR hP iX jp kN mO oU qT rS aP bT co dO eM fr gq hW iS jR kQ lX mN nU pV ar bg cS dX eV fh iR jP kT lM mU nW oQ pN qO aU bX cR dk eO fP gW hS ir jV ln mM oN pT qQ aT bR cU dS eN fi go hO jQ km lV nM pW qX rP aM bO cQ dT eq fo gP hV in jN kS lU mX pR rW aN bj cT do eS fQ gX hU iV kO lq mW nR pP rM ak bN cV dM em fR gp hX iQ jU lP nS oO qW rT aR bn cN dq eP fX gT hM iO jS kU lp mV oW rQ aHO ahK ajW aqA bKS bip bmD bqU cIP cgH chn cjr dAV dGR djD dlW eFT eJU ehp ekr fBN fmF fnV fqM gES gLN grO hCQ iFP iGW iJT jCX kEX kJM kqV lIQ lLR loB mBR mHP nAQ nEO oGX oIM oLT pCS pDU rKN Figure 1. A partition of K6,6,6,12,12 Proof. Let {Gi : 1 ≤ i ≤ 5} be groups of size g,g,g,u,u respectively and set G = ⋃5 i=1 Gi. Let {Hi : 1 ≤ i ≤ 5} be groups of size a,a,a,b,b respectively and set H = ⋃5 i=1 Hi. If x ∈ G , then we denote by x, the w-element set x = x× Zw and set Gi = ⋃ x∈Gi x. If h ∈ H , then we denote by h, the (w − 1)-element set x = x × (Zw \{0}) and set Hi = ⋃ h∈Hi h. We construct the 3-gdd of type (wg + (w − 1)a)3(wu + (w − 1)b)2 on groups {(Gi ∪ Hi) : 1 ≤ i ≤ 5}. P(x,y,z) and D(x,y,z) are as in the proof of Theorem 4.7. Let A be a 3-igdd of type (g + a : a)3(u + b : b)2 on the groups (Gi ∪Hi), i = 1,2,3,4,5 and hole H . Let B be a 3-gdd of type g3u2 on the groups Gi, i = 1,2,3,4,5. To construct the 3-gdd of type (wg+(w−1)a)3(wu+(w−1)b)2 we take the triples in: {{h×{j},x× {i},y ×{i + j mod w}} : i,j ∈ Zw,j 6= 0} whenever { h,x,y } is a triple in A intersecting the hole H in 143 C. J. Colbourn et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 135–144 the point h; D(x,y,z) whenever { x,y,z } is a triple in A disjoint from the hole H ; P(x,y,z) whenever{ x,y,z } is a triple in B; and a 3-gdd of type ((w −1)a)3((w −1)b)2 on the hole ⋃5 i=1 Hi. Corollary 4.10. There exists a 3-gdd of type 113152. Proof. There exist 3-gdds of types 3332 and 1332 and a 3-igdd of type (4 : 1)3(6 : 3)2. Apply Theo- rem 4.9 with w = 3. Lemma 4.11. There exists a 3-gdd of type 113212. Proof. Figure 1 provides a partition of K6,6,6,12,12 that was found using a hill-climbing algorithm on points a-r and A-X with groups G1 = a-f, G2 = g-l, G3 = m-r, G4 = A-L, and G5 = M-X into five holey parallel classes of pairs for each of G1, G2, and G3; nine holey parallel classes of pairs for each of G4 and G5; and 48 triples. To form a 3-igdd of type (11 : 5)3(21 : 9)2, extend the holey parallel classes. Then fill the hole with a 3-gdd of type 5392. This completes the proof of the Main Theorem. References [1] D. Bryant, D. Horsley, Steiner triple systems with two disjoint subsystems, J. Combin. Des. 14(1) (2006) 14–24. [2] C. J. Colbourn, Small group divisible designs with block size three, J. Combin. Math. Combin. Com- put. 14 (1993) 153–171. [3] C. J. Colbourn, C. A. Cusack, D. L. Kreher, Partial Steiner triple systems with equal-sized holes, J. Combin. Theory Ser. A 70(1) (1995) 56–65. [4] C. J. Colbourn, J. H. Dinitz (Eds.), Handbook of Combinatorial Designs, Second Edition, CRC/Chapman and Hall, Boca Raton, FL, 2007. [5] C. J. Colbourn, D. Hoffman, R. Rees, A new class of group divisible designs with block size three, J. Combin. Theory Ser. A 59(1) (1992) 73–89. [6] C. J. Colbourn, M. A. Oravas, R. S. Rees, Steiner triple systems with disjoint or intersecting subsys- tems, J. Combin. Des. 8(1) (2000) 58–77. [7] R. Rees, Uniformly resolvable pairwise balanced designs with blocksizes two and three, J. Combin. Theory Ser. A 45(2) (1987) 207-225. [8] R. M. Wilson, An existence theory for pairwise balanced designs. I. Composition theorems and mor- phisms, J. Combinatorial Theory Ser. A 13 (1972) 220–245. [9] R. M. Wilson, An existence theory for pairwise balanced designs. II. The structure of PBD-closed sets and the existence conjectures, J. Combinatorial Theory Ser. A 13 (1972) 246–273. 144 http://dx.doi.org/10.1002/jcd.20071 http://dx.doi.org/10.1002/jcd.20071 http://www.ams.org/mathscinet-getitem?mr=1238867 http://www.ams.org/mathscinet-getitem?mr=1238867 http://dx.doi.org/10.1016/0097-3165(95)90080-2 http://dx.doi.org/10.1016/0097-3165(95)90080-2 http://dx.doi.org/10.1016/0097-3165(92)90099-G http://dx.doi.org/10.1016/0097-3165(92)90099-G http://dx.doi.org/10.1002/(SICI)1520-6610(2000)8:1<58::AID-JCD8>3.0.CO;2-2 http://dx.doi.org/10.1002/(SICI)1520-6610(2000)8:1<58::AID-JCD8>3.0.CO;2-2 http://dx.doi.org/10.1016/0097-3165(87)90015-X http://dx.doi.org/10.1016/0097-3165(87)90015-X http://www.ams.org/mathscinet-getitem?mr=0304203 http://www.ams.org/mathscinet-getitem?mr=0304203 http://www.ams.org/mathscinet-getitem?mr=0304204 http://www.ams.org/mathscinet-getitem?mr=0304204 Introduction 3-GDDs of type g3u2 Incomplete group divisible designs Using incomplete group divisible designs References