We obtain several results towards the proof that the necessary conditions are sufficient for the existence of a GDD\((n_1 = 1, n_2 = n, 4; \lambda_1, \lambda_2)\) where \(\lambda_1 \ge \lambda_2\). We also have some general results including the constructions for larger block sizes as well as when the first group size \(n_1\) is not 1 or \(\lambda_1 < \lambda_2\).
Group divisible designs (GDDs) are classical combinatorial designs studied for their applications as well as for their own sake. GDDs are inherently hard to construct, especially when the number of groups is less than the block size and group sizes are different.
For block size 3, a lot of work on GDDs is done. For example, Fu, Rodger and Sarvate [12, 13] obtained complete results on the existence of group divisible designs with block size \(3\) and \(m\) groups of size \(n\). Colbourn, Hoffman and Rees [8] proved the sufficiency of the necessary conditions for the existence of GDDs denoted as GDD\((n, n, …, n, u, 3;0, 1)\), where one of the groups is of size \(u \neq n\) (\(n\) is the size of other groups). The study of GDDs with unequal group sizes is more difficult in general. Pabhapote and Punnim [16] studied all triples of positive integers \((n_1, n_2, \lambda)\) for which GDD\((n_1, n_2, 3;\lambda, 1)\) exists. They proved that the necessary conditions are sufficient for the existence of a GDD\((n_1, n_2, 3;\lambda, 1)\). Later, Pabhapote [15] proved the existence of a GDD\((n_1, n_2, 3;\lambda_1, \lambda_2)\) for all \(n_1 \ne 2\) and \(n_2 \ne 2\) in which \(\lambda_1\ge \lambda_2\). Chaiyasena, Hurd, Punim and Sarvate [6] obtained general results for GDDs with three groups of different sizes denoted by GDD\((n_1, n_2, n_3, 3;\lambda_1,\) \(\lambda_2)\). GDDs with block size four and different group sizes are not widely studied. Forbes showed that the necessary conditions for the existence of a GDD\((n, n, …, n, u, 4;0, 1)\) are sufficient for a range of different values of \(n\) and \(u\) [9, 10, 11]. Abel et al. studied the existence of a GDD\((n_1, n_2, 4; 0, 1)\) for a range of different values of \(n_1\) and \(n_2\) [1, 2, 3, 4, 5, 17]. Hunde and Woldemariam studied GDD\((n_1, n_2, 4; \lambda,\lambda_2)\) where \(\lambda_2 = 1, 2\) [14].
The subject matter for this paper is to study GDDs with two groups of different sizes where the first group is of size 1 and the block size is 4. We begin with necessary definitions.
Definition 1.1. A Balanced Incomplete Block Design, BIBD\((v, b, k, r, \lambda)\), is a pair \((V, \mathcal{B})\), where \(V\) is a \(v\)-set of elements and \(\mathcal{B}\) is a collection of \(b\) \(k\)-subsets of \(V\) called blocks \((k < v)\) such that every element appears in \(r\) blocks, and every pair of distinct elements appears in exactly \(\lambda\) blocks. Unless we need to specify the values of \(b\) or \(r\), we use the notation BIBD\((v, k, \lambda)\).
Definition 1.2. A parallel class in a BIBD\((v,k,\lambda)\) is a set of disjoint blocks of the BIBD whose union is V. A partition of the collection of all blocks into \(r\) parallel classes is called a resolution. A BIBD is said to be a resolvable BIBD, denoted RBIBD\((v, k, \lambda)\) if it has a resolution.
A pairwise balanced design (PBD\((v, K, \lambda)\)) is a block design of \(v\) points such that any two distinct points lie in \(\lambda\) blocks, where \(K\) is the set of cardinalities of blocks. If \(\lambda = 1\), we denote it as PBD\((v, K)\). A resolvable PBD\((v, K)\) is denoted as RPBD\((v, K)\). If all parallel classes of a RPBD\((v, K)\) contain blocks of one size \(k\), then it is said to be uniformly resolvable and is denoted as URD\((v, K)\). The number of parallel classes in a URD\((v, K)\) with blocks of size \(k\) is denoted as \(r_k, k \in K\).
We need the following theorems for our work.
Theorem 1.3. [7] A BIBD\((v,3,\lambda)\) exists iff any of the following necessary conditions are satisfied:
A BIBD\((v,3,\lambda)\) where \(\lambda \equiv 1,5\pmod 6\) exists iff \(v \equiv 1, 3\pmod 6\).
A BIBD\((v,3,\lambda)\) where \(\lambda\equiv 2,4\pmod 6\) exists iff \(v \equiv 0, 1\pmod 3\).
A BIBD\((v,3,\lambda)\) where \(\lambda\equiv 3 \pmod 6\) exists iff \(v \equiv 1\pmod 2\).
A BIBD\((v,3,\lambda)\) where \(\lambda\equiv 0\pmod 6\) exists iff \(v\geq 3\).
Theorem 1.4. [7] A BIBD\((v,4,\lambda)\) exists iff any of the following necessary conditions are satisfied:
\(\lambda \equiv 1, 5 \pmod 6\) and \(v \equiv 1, 4 \pmod{12}\);
\(\lambda\equiv2,4\pmod6\) and \(v\equiv1\pmod3\);
\(\lambda\equiv3\pmod6\) and \(v\equiv0,1\pmod4\);
\(\lambda\equiv0\pmod6\) and \(v\ge 4\).
Theorem 1.5. [18] There exists a URD\((v, \{3, 4\})\) with \(r_3, r_4 > 0\) if and only if \(v \equiv 0 \pmod {12}\), \(r_4\) is odd and \(1 \le r_4 \le \frac{v}{3} – 1\), except for \(v = 12\) and \(r_4 = 3\).
Note that \(r_3\) and \(r_4\) are related. If \(x\) is an element in \(r_4\) blocks of size 4, then \(x\) is appearing with \(3r_4\) elements in the blocks of size 4. Therefore, \(x\) has to appear with the remaining \(v – 1 – 3r_4\) elements in block of size 3, we have \(r_3 = \frac{v – 1 – 3r_4}{2}\).
Definition 1.6. A group divisible design, GDD\((n_1, n_2,…,n_m, k; \lambda_{1}, \lambda_{2})\), is a triple \((X, \mathcal{G}, \mathcal{B})\), where \(X\) is a \(v\)-set (\(v = n_1 + n_2 + … + n_m\)), \(\mathcal{G}\) a partition of \(X\) into \(m\) subsets (called groups) of size \(n_1, n_2, …, n_m\) respectively and \(\mathcal{B}\) is a collection of \(k\)-subsets of \(X\) (called blocks) such that
(i) the pairs of points within the same group, called first associates of each other, appear together in \(\lambda_1\) blocks, and
(ii) the pairs of points not in the same group, called second associates of each other, appear together in \(\lambda_2\) blocks.
If \(n_1 = n_2 = \cdots = n_m = n\), it is denoted as a GDD\((n, m, k; \lambda_1, \lambda_2)\). To avoid confusion of the notation of GDDs with two groups of unequal sizes and block size 4, GDD\((n_1, n_2, 4;\lambda_1, \lambda_2)\), we specify the sizes of the two groups as \(n_1\) and \(n_2\), in the remaining of this paper unless \(n_1 = 1\).
An important result for \(k = 4\) and \(\lambda_1 = 0\) and \(\lambda_2 = \lambda\) [7] is as follows.
Theorem 1.7. Necessary conditions for the existence of a GDD\((n, m, 4;\) \(0, \lambda)\) given below
(i) \(m \ge 4\) and
(ii) \(\lambda n (m – 1) \equiv 0 \pmod 3\) and
(iii) \(\lambda m (m – 1)n^2
\equiv 0 \pmod {12}\)
are sufficient where \((n, m, \lambda) \neq
(2, 4, 1)\) and \((n, m, \lambda) \neq
(6, 4, 1)\).
It is well known that the blocks of the BIBDs can be used as the building blocks of GDDs. For example, we will use the following construction repeatedly by combining the blocks of the two BIBDs.
Theorem 1.8. If a BIBD\((n_1+n_2+ … +n_m, k, \lambda_2)\) and a BIBD\((n_i, k, \lambda_1)\) exist for \(i = 1, 2, … m\), then GDD\((n_1,n_2,…,n_m,k;\lambda_1+\lambda_2,\lambda_2)\) exists.
Another such construction given below is very useful to construct a GDD\((1, n, k; \lambda_1, \lambda_2)\), not only for \(\lambda_1 \geq \lambda_2\), but also for \(\lambda_1 < \lambda_2\). Even though keeping with the tradition of papers [14, 15, 16], we study in this note designs where \(\lambda_1 \geq \lambda_2\).
Theorem 1.9. If a BIBD\((v = n, b, r, k, \lambda)\) and a BIBD\((v = n, k + 1, \Lambda)\) exist, then a GDD\((n_1 = 1, n_2 = n, k + 1; \lambda + u\Lambda, r)\) exists where \(u\) is a nonnegative integer.
Proof. Let \(G_1 = \{x\}\) and \(G_2 = \{1, \cdots, n\}\). The blocks of the required GDD\((n_1 = 1, n_2 = n, k + 1; \lambda + u\Lambda, r)\) are obtained by combining \(u\) copies of the blocks of the BIBD\((n, k + 1, \Lambda)\) on \(G_2\), with the blocks obtained by taking union of \(G_1\) with the blocks of the BIBD\((n, b, r, k, \lambda)\) on \(G_2\). ◻
We can have many corollaries from Theorem 1.9, for different values of \(k\) depending on the existence of BIBDs, but we are specifically interested in the following result.
Corollary 1.10. A BIBD\((v, b, r, 3, 1)\) and a BIBD\((v, 4, 2t)\) where \(v = 12s + 7\) and \(r = 6s + 3\) exist, therefore, a GDD\((n_1 = 1, n_2 = v, 4; \lambda_1 = 2t + 1, \lambda_2 = r)\) exists where \(s\) and \(t\) are nonnegative integers.
Corollary 1.10 gives specific examples for the case \(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 1, 5 \pmod{6}\) and \(n \equiv 7 \pmod{12}\) of Theorem 6.8.
Using Theorem 1.4 and Theorem 1.8, we obtain the following families.
Theorem 2.1. The following GDDs exist:
(i) A GDD\((n_1, n_2, 4; \lambda + 6s, \lambda)\) where \(\lambda \equiv 1, 5 \pmod{6}\) exists for \(n_1 + n_2 \equiv 1, 4\pmod {12}\) and \(n_i \ge4\) for \(i = 1, 2\) and any nonnegative integer \(s\).
(ii) A GDD\((n_1, n_2, 4; \lambda + 6s, \lambda)\) where \(\lambda = 2, 4 \pmod{6}\) exists for \(n_1 + n_2 \equiv1\pmod{3}\) and \(n_i \ge4\) for \(i=1,2\) and any nonnegative integer \(s\).
(iii) A GDD\((n_1, n_2, 4; \lambda + 6s, \lambda)\) where \(\lambda = 3 \pmod{6}\) exists for \(n_1 + n_2 \equiv 0, 1\pmod{4}\) and \(n_i \ge4\) for \(i=1,2\) and any nonnegative integer \(s\).
(iv) A GDD\((n_1, n_2, 4; \lambda + 6s, \lambda)\) where \(\lambda = 0 \pmod{6}\) exists for \(n_i \ge 4\) for \(i=1,2\) and any nonnegative integer \(s\).
Theorem 2.2. (a) If a URD\((v, \{3, 4\}, \lambda)\) exists with \(r_3\) parallel classes of block size three, then a GDD\((n_1 = 1, n_2 = v, 4; \lambda, \lambda_2 = r_3)\) exists.
(b) If a URD\((v, \{3, 4\}, \lambda)\) exists with \(r_3\) parallel classes, then a GDD\((n_1 = 4, n_2 = v, 4; 4\lambda, r_3)\) exists.
Proof. (a) First we union the first group \(G_1\) of size 1 with each block of size three from the URD\((v, \{3, 4\}, \lambda)\). The resulting blocks are then combined with the blocks of size four from the URD\((v, \{3, 4\}, \lambda)\). As a result, we have a GDD\((n_1 = 1, n_2 = v, 4; \lambda, \lambda_2 = r_3)\).
(b) Let \(G_1 = \{1, 2, 3, 4\}\), disjoint from the second group \(G_2\) of size \(v\). Take four copies of the URD\((v, \{3, 4\}, \lambda)\) on \(G_2\). In the \(i^{th}\) copy of the URD (for \(i = 1, 2, 3, 4\)), replace blocks of size 3 by the blocks of size 4 obtained by combining each block of size 3 with element \(i\) of \(G_1\). These blocks along with \(4\lambda\) copies of \(G_1\) as blocks give the required design. ◻
Using Theorem 1.5, we have the following results.
Theorem 2.3. (a) For \(v \equiv 0 \pmod {12}, v > 12\), a GDD\((n_1 = 4, n_2 = v, 4; 4, r_3)\) exists for \(r_3 = \frac{v – 1 – 3r_4}{2}\) and \(1 \le r_4 \le \frac{v}{3} – 1\). For \(v = 12\), a GDD\((n_1 = 4, n_2 = 12, 4; 4, 1)\) exists.
(b) For \(n \equiv 0 \pmod {12}, n > 12\), using URD with \(r_3 = 4\), a GDD\((n_1 = 1, n_2 = n, 4; 1, 4)\) exists and a GDD\((n_1 = 1, n_2 = n, 4; 6s + 1, 6t + 4)\) exists.
In this section, we present some constructions of GDD\((n_1 = 1, n_2\) \(= n, 4;\lambda_1,\lambda_2)\), using known designs as building blocks.
Theorem 3.1. If a GDD\((n = 3, m, 4;0, \lambda)\) exists and a BIBD\((3m, 4, \mu)\) exists, then a GDD\((n_1 = 1, n_2 = 3m, 4;\mu + \lambda, \lambda)\) exists.
Proof. We divide \(3m\) elements of the second group \(G_2\) into \(m\) groups of size 3 each, and construct the blocks of a GDD\((n = 3, m, 4;0, \lambda)\). These blocks together with the blocks of a BIBD\((3m, 4, \mu)\) on \(G_2\) give the blocks of a GDD\((n = 3, m, 4; \mu, \mu + \lambda)\). Next, we form blocks of size 4 by taking union of \(G_1 = \{x\}\) with each of the \(m\) groups to the three elements of \(G_2\). Now, \(\lambda\) copies of such blocks along with the blocks of the GDD\((n = 3, m, 4; \mu, \mu + \lambda)\) formed previously give us a GDD\((n_1 = 1, n_2 = 3m, 4;\mu + \lambda, \lambda)\). ◻
As the necessary and sufficient conditions for the existence of a GDD\((n\) \(= 3, m, 4;0, \lambda)\) are \(m \geq 4\), \(\lambda m(m – 1)\equiv 0 \pmod{4}\), and the necessary and sufficient conditions for the existence of a BIBD\((3m, 4, \mu)\) are (i) \(\mu \equiv 3 \pmod{6}\) and \(m \equiv 0, 3 \pmod{4}\); or (ii) \(\mu \equiv 0 \pmod{6}\) and any \(m \ge 2\), we have the following corollary.
Corollary 3.2. For any even \(\lambda_2\), say \(2t\), a GDD\((n_1 = 1, n_2 = 3m, 4; \lambda_ 1\) \(= 6s + 2t + 3, \lambda_2 = 2t)\) for \(m \equiv 0, 3 \pmod{4}\) and a GDD\((n_1 = 1, n_2 = 3m, 4; \lambda_ 1 = 6s + 2t, \lambda_2 = 2t)\) for \(m \geq 2\) and any nonnegative integers \(s\) and \(t\) exists.
Theorem 3.3. If a GDD\((n, m, 4;0, 1)\) exists, then a GDD\((n_1 = 1, n_2 = nm, 4; n – 2, \binom{n – 1}{2})\) exists.
Proof. Let \(G_1 = \{x\}\) and \(G_2 = \{1, 2, \cdots, nm\}\). Let the groups of the GDD\((n, m, 4;0, 1)\) be a partition \(H_1\), \(\cdots, H_m\) of \(G_2\) where each \(H_i\) is of size \(n\). Also, let \(T_i\) be the collection of all triples of \(H_i\), \(i = 1, \cdots, m\), i.e., \(T_i = \{\{a, b, c\} | \{a, b, c\} \subseteq H_i\}\), and let \(T = \cup_{i=1}^{m}T_{i}\).
Let \(B_1\) be the collection of blocks of size 4 by adding \(x\) to each triple in \(T\), and \(B_2\) be the blocks of the GDD\((n, m, 4;0, 1)\). Then \(n – 2\) copies of \(B_2\) along with the blocks of \(B_1\) form the required GDD\((n_1 = 1, n_2 = nm, 4; n – 2, \binom{n}{2})\).
To check \(\lambda_1 = n – 2\), observe that if two elements are in a group \(H_i\), then they occur in \(n – 2\) triples in \(T\) as the size of \(H_i\) is \(n\). If two elements are in different groups, say \(H_i\) and \(H_j (i \neq j)\), then in \(B_2\) they occur only once, hence they occur \(n – 2\) times as we have \(n – 2\) copies of \(B_2\).
To check \(\lambda_2 = \binom{n – 1}{2}\), consider a pair, say \((a, x)\), if \(a\) is in \(H_i\), then \(a\) occurs in \(\binom{n – 1}{2}\) subsets of \(H_i\). Hence, the pair \((a, x)\) occurs in \(\binom{n – 1}{2}\) blocks from \(B_1\). ◻
From Theorem 1.7, a GDD\((4, m, 4;0, 1)\) exists for \(m \equiv 1 \pmod{3}\), and we have:
Corollary 3.4. A GDD\((n_1 = 1, n_2 = 4m, 4;2, 3)\) exists for \(n_2 \equiv 4 \pmod{12}\).
Assuming a GDD(\(1\), \(n\), \(4\);\(\lambda_{1}\), \(\lambda_{2}\)) exists, we count the replication number \(r_{i}\) of elements of the \(i^{th}\) group for \(i\) = \(1\), \(2\) and the required number of blocks \(b\).
Theorem 4.1. If a GDD(\(1\), \(n\), \(4\); \(\lambda_{1}\), \(\lambda_{2}\)) exists, then
(i) \(r_{1}\)=\(\frac{n\lambda_2}{3}\), therefore, \(n\lambda_2 \equiv 0 \pmod 3\);
(ii) \(r_{2}\)=\(\frac{(n-1)\lambda_1 +\lambda_{2}}{3}\), therefore, \((n-1)\lambda_1 +\lambda_{2} \equiv 0 \pmod 3\);
(iii) \(b\)=\(\frac{n(n-1)\lambda_{1}+2n\lambda_{2}}{12}\), therefore, \(n(n-1)\lambda_{1}+2n\lambda_{2} \equiv 0 \pmod {12}\).
Proof. (i). Let \(G_1 = \{x\}\). Then \(x\) appears in \(r_{1}\) blocks of the design, and there are 3 pairs containing \(x\) in each block. Hence, there are \(3r_{1}\) pairs containing \(x\). Second, there are \(n\) ways of choosing an element from the second group to form a pair with \(x\), and it occurs in \(\lambda_{2}\) blocks. That is, there are \(n\lambda_{2}\) pairs containing \(x\). Hence, \(3r_{1} = n\lambda_{2}\), and \(r_{1} = \frac{n\lambda_2}{3}\).
(ii). Let an element of the second group, say \(y\), occurs in \(r_{2}\) blocks. In each of these blocks, there are 3 pairs containing \(y\). Hence, there are \(3r_{2}\) pairs containing \(y\). On the other hand, there are \((n-1)\lambda_{1} + \lambda_{2}\) pairs in the design containing \(y\). Therefore, \(3r_{2} = (n-1)\)\(\lambda_{1} + \lambda_{2}\). Hence, \(r_{2} = \frac{(n-1)\lambda_1+\lambda_{2}}{3}\).
(iii). In a design with block size \(4\) and \(b\) blocks, there are \(b\)\(4\choose2\)=\(6b\) pairs. On the other hand, there must be exactly \(n\choose2\)\(\lambda_{1}\) pairs of type \((2,0)\) and \(n\)\(\lambda_{2}\) pairs of type \((1,1)\) in the design. Therefore, \(6b =\) \(n\choose2\) \(\lambda_{1}\)+\(n\)\(\lambda_{2}\) and \(b = \frac{n(n-1)\lambda_{1}+2n\lambda_{2}}{12}\). ◻
Theorem 4.2. If a GDD(\(1\), \(n\), \(4\);\(\lambda_{1}\), \(\lambda_{2}\)) exists, then
(a) \(b \geq\) max \(\{r_{1}+r_{2}-\lambda_{2}, 2r_{2}-\lambda_{1} \};\)
(b) \(b\leq\frac{n(n-1)\lambda_{1}}{6}\);
(c) \(\lambda_{2}\)\(\leq\)\(\frac{(n-1)\lambda_{1}}{2},\) i.e. \(\lambda_1 \geq \frac{2\lambda_2}{n – 1};\)
Proof. (a) Consider the following two cases: (i) if \(x\) and \(y\) are elements chosen from different groups (say \(x\) is from the first group and \(y\) is from the second group), then there are \(r_{1}\) blocks containing \(x\) and \(r_{2}-\lambda_{2}\) blocks containing \(y\) but not \(x\). Hence, there are at least \(r_{1}+ r_{2} – \lambda_{2}\) blocks in the GDD.
(ii) When \(x\) and \(y\) are from the same group \(G_{2}\), there are \(r_{2}\) blocks containing \(x\) and \(r_{2}-\lambda_{1}\) blocks containing \(y\) but not \(x\), which implies there are at least \(2r_{2} – \lambda_{1}\) blocks.
From \((i)\) and \((ii)\), the (b) follows.
(b) If a GDD(\(1\), \(n\), \(4\);\(\lambda_{1}\), \(\lambda_{2}\)) exists, then every block contains at least \(3\) first associate pairs. This means \(\lambda_{1}\)\(n\choose2\) \(\geq 3b\) (where \(\lambda_{1}\)\(n\choose 2\) is the number of first associate pairs in the design), and \(b\leq\frac{n(n-1)\lambda_{1}}{6}\).
(c) From Theorem 4.1 and (b), \(b = \frac{n(n-1)\lambda_1+2n\lambda_2}{12} \leq \frac{n(n – 1)\lambda_1}{6}\), which is equivalent to \(2n\lambda_2 \leq (n – 1)n\lambda_1\), that is, \(\lambda_2 \leq \frac{(n-1)\lambda_1}{2}\). ◻
Theorem 4.2 provides us one of the necessary conditions for the existence of a GDD(\(1, n,\\ 4;\lambda_{1}, \lambda_{2}\)): \(\lambda_2 \leq \frac{(n-1)\lambda_1}{2}\). Furthermore, necessary conditions on \(n\) are given below where \(n\) is equal to the values specified in each entry and DNE means “does not exist”.
Let \(G_1 = \{x\}\), \(G_2 = \{1, 2, \cdots, n\}\). For \(n = 4\), \(\lambda_1 \geq \frac{2\lambda_2}{3}\) from the necessary condition in Theorem 4.2. From Table 1, we have two cases for \(n = 4\): \(\lambda_2 \equiv 0 \pmod{6}\) and any \(\lambda_1\); \(\lambda_2 \equiv 3 \pmod{6}\) and any \(\lambda_1\). These two cases are equivalent to \(\lambda_2 \equiv 0 \pmod{3}\), i.e., \(\lambda_2 = 3t\). Since \(\lambda_1 \geq \frac{2\lambda_2}{3}\), we have \(\lambda_1 \geq 2t\).
[0.9]
| \(\lambda_1 \backslash\lambda_2\) | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | all \(n \geq 3\) | DNE | DNE | \(0 \pmod 2\) | DNE | DNE |
| 1 | \(1, 4\pmod {12}\) | \(0, 3\pmod{12}\) | DNE | \(4, 7 \pmod{12}\) | \(0, 9 \pmod{12}\) | DNE |
| 2 | \(1 \pmod 3\) | DNE | \(0 \pmod 3\) | \(4 \pmod 6\) | DNE | \(0 \pmod 6\) |
| 3 | \(0, 1 \pmod 4\) | DNE | DNE | \(0, 3\pmod 4\) | DNE | DNE |
| 4 | \(1 \pmod 3\) | \(0 \pmod 6\) | DNE | \(4 \pmod 6\) | \(0 \pmod 3\) | DNE |
| 5 | \(1, 4\pmod{12}\) | DNE | \(0, 9 \pmod {12}\) | \(4, 7 \pmod{12}\) | DNE | \(0, 3 \pmod{12}\) |
Example 5.1. Combining the blocks \(\{1, 2, 3, x\}\), \(\{1, 2, 4, x\}\), \(\{1, 3, 4, x\}\), and \(\{2, 3, 4, x\}\) with \(\lambda_1 – 2\) copies of \(\{1, 2, 3, 4\}\) gives us a GDD\((1, 4, 4; \lambda_1, 3)\). Similarly, union \(G_1\) with the blocks of a BIBD\((4, 3, 2t)\) on \(G_2\), and then combining these resulting blocks and \(\lambda_1 – 2t\) copies of \(\{1, 2, 3, 4\}\) give us a GDD\((1, 4, 4; \lambda_1, 3t)\) where \(\lambda_1 \ge 2t\), as required by the necessary condition \(\lambda_1 \geq \frac{2\lambda_2}{n – 1}\) from Theorem 4.2.
Example 5.1 gives:
Corollary 5.2. The necessary conditions (given in Table 1 and Theorem 4.2) are sufficient for the existence of a GDD\((1, 4, 4; \lambda_1, \lambda_2)\).
For \(n = 5\), we have only one case \(\lambda_1 \equiv 3 \pmod{6}\) and \(\lambda_2 \equiv 0 \pmod{6}\) from Table 1. Let \(\lambda_2 = 6s\), we have \(\lambda_1 \geq 3s\) by the necessary condition \(\lambda_1 \geq \frac{2\lambda_2}{n – 1}\) from Theorem 4.2.
Example 5.3. Joining \(G_1\) with every 3-subset of \(G_2 = \{1, 2, 3, 4, 5\}\) gives us a GDD\((1, 5,\\ 4; 3, 6)\). Furthermore, combining \(s\) copies of the blocks of a GDD\((1, 5, 4; 3, 6)\) with \(3t – 3s\) (where \(t \ge s\)) copies of every 4-subset of \(G_2\) results in a GDD\((1, 5, 4; 3t, 6s)\), again notice that the necessary condition \(\lambda_1 \geq \frac{2\lambda_2}{n – 1}\) is satisfied.
Example 5.3 gives:
Corollary 5.4. The necessary conditions (given in Table 1 and Theorem 4.2) are sufficient for the existence of a GDD\((1, 5, 4; \lambda_1, \lambda_2)\).
Example 5.5. A GDD\((1, 6, 4; 4, 1)\) has the blocks \(\{1, 2, 3, x\}\), \(\{4, 5, 6, x\}\), \(\{1, 2, 4, 5\}\), \(\{1, 2, 4, 6\}\), \(\{1, 2, 5, 6\}\), \(\{1, 3, 4, 5\}\), \(\{1, 3, 4, 6\}\), \(\{1, 3, 5, 6\}\), \(\{2, 3, 4,\) \(5\}\), \(\{2, 3, 4, 6\}\), and \(\{2, 3,\\ 5, 6\}\). In addition, for \(\lambda_1 \equiv 4 \pmod 6 = 6t + 4\) where \(t\) is a nonnegative integer, by combining the blocks of \(t\) copies of a BIBD\((6, 4, 6)\) and the blocks of a GDD\((1, 6, 4; 4, 1)\), we have a GDD\((1, 6, 4;\) \(\lambda_1, 1)\).
Example 5.6. A GDD\((1, 6, 4; 4, 7)\) has the blocks \(\{1, 2, 3, 4\}\), \(\{3, 4, 5, 6\}\), \(\{1, 2, 5, 6\}\) \(\{1, 2,\\ 3, x\}\), \(\{1, 2, 4, x\}\), \(\{3, 4, 5, x\}\), \(\{3, 4, 6, x\}\), \(\{1, 5, 6, x\}\), \(\{2, 5, 6,\) \(x\}\), \(\{1, 3, 5, x\}\), \(\{1, 3, 6, x\}\), \(\{1, 4, 5, x\}\), \(\{1, 4, 6, x\}\), \(\{2, 3, 5, x\}\), \(\{2, 3, 6, x\}\), \(\{2, 4, 5, x\}\) and \(\{2, 4, 6, x\}\). In addition, for \(\lambda_1 \equiv 4 \pmod 6 = 6t + 4\) where \(t\) is a nonnegative integer, by combining the blocks of \(t\) copies of a BIBD\((6, 4, 6)\) and the blocks of a GDD\((1, 6, 4; 4, 7)\), we have a GDD\((1, 6, 4;\) \(\lambda_1, 7)\).
Example 5.7. A BIBD\((7, 4, 4)\) can be considered as a GDD\((1, 6, 4; 4, 4)\). The blocks of a GDD\((1, 6, 4; 4, 10)\) are obtained by taking the union of \(G_1\) with each block of BIBD\((6, 3, 4)\) on \(G_2\).
Note that if \(n = 6\) and \(\lambda_1 = 4\), one of the necessary conditions \(\lambda_{2} \leq \frac{(n-1)\lambda_{1}}{2}\) implies that \(\lambda_2 \leq 10\). From the necessary conditions in Table 1, if \(\lambda_1 \equiv 4 \pmod 6\), then \(\lambda_2 \equiv 1 \pmod 6\) or \(\lambda_2 \equiv 4 \pmod 6\). This implies the necessary conditions of a GDD\((1, 6, 4; 4, \lambda_2)\) are sufficient from Examples 5.5, 5.6 and 5.7.
Example 5.8. Since a BIBD\((7, 4, 6)\) is also a GDD\((1, 6, 4; 6, 6)\), by combining the blocks of a BIBD\((7, 4, 6)\) and the blocks of a GDD\((1, 6, 4; 4, 7)\), we have a GDD\((1, 6, 4; 10, 13)\). In addition, for \(\lambda_1 \equiv 4 \pmod 6 = 6t + 4\) where \(t\) is a nonnegative integer, by combining the blocks of \(t\) copies of a BIBD\((6, 4, 6)\) and the blocks of a GDD\((1, 6, 4; 4, 7)\), we have a GDD\((1, 6, 4;\) \(\lambda_1, 13)\).
In general, we have many cases to consider for \(n = 6\):
(1) \(\lambda_1 \equiv 0 \pmod{6}\) and \(\lambda_2 \equiv 0 \pmod{6}\);
(2) \(\lambda_1 \equiv 0 \pmod{6}\) and \(\lambda_2 \equiv 3 \pmod{6}\);
(3) \(\lambda_1 \equiv 2 \pmod{6}\) and \(\lambda_2 \equiv 2 \pmod{6}\);
(4) \(\lambda_1 \equiv 2 \pmod{6}\) and \(\lambda_2 \equiv 5 \pmod{6}\);
(5) \(\lambda_1 \equiv 4 \pmod{6}\) and \(\lambda_2 \equiv 1 \pmod{6}\);
(6) \(\lambda_1 \equiv 4 \pmod{6}\) and \(\lambda_2 \equiv 4 \pmod{6}\).
We restrict our attention to \(\lambda_1 \geq \lambda_2\) in these cases.
In Section 6, existence is shown along with general values of \(n\) for three cases ((1), (3) and (6)), except for cases (2), (4) and (5). These cases are taken care of below:
Case 2. Let \(\lambda_1 = 6s\) and \(\lambda_2 = 6t + 3\) where \(s \geq t\). Since we assume \(\lambda_1 \geq \lambda_2\), \(6s \geq 6t + 3\), i.e. \(s \geq \lceil t + \frac{1}{2} \rceil = t + 1\). Using Example 5.5, we have a GDD\((1, 6, 4; 4, 1)\). Combining the blocks of a GDD\((1, 6, 4; 4, 1)\) with the blocks of a BIBD\((7, 4, 6t + 2)\) on \(G_1 \cup G_2\) (where \(G_1\) is the first group and \(G_2\) is the second group) and \(s – t – 1\) copies of the blocks of a BIBD\((6, 4, 6)\) on \(G_2\) give us the blocks of a GDD\((1, 6, 4; \lambda_1 = 6s, \lambda_2 = 6t + 3)\).
Case 4. Let \(\lambda_1 = 6s + 2\) and \(\lambda_2 = 6t + 5\) where \(s \geq t\). Union the first group \(G_1\) with the blocks of a BIBD\((6, 3, 2)\) on the second group \(G_2\) give us the blocks of a GDD\((1, 6, 4; 2, 5)\). Combining these blocks with the blocks of a BIBD\((7, 4, 6t)\) on \(G_1 \cup G_2\), we get a GDD\((1, 6, 4; 6t + 2, 6t + 5)\). The blocks of a GDD\((1, 6, 4; 6t + 2, 6t + 5)\) combined with the blocks of a BIBD\((6, 4, 6s – 6t)\) on \(G_2\) give us the blocks of a GDD\((1, 6, 4; \lambda_1 = 6s + 2, \lambda_2 = 6t + 5)\).
Case 5. Let \(\lambda_1 = 6s + 4\) and \(\lambda_2 = 6t + 1\) where \(s \geq t\). Note that a BIBD\((7, 4, 6t + 1)\) cannot be used since it does not exist. Combining the blocks of a GDD\((1, 6, 4; 4, 1)\) (using Example 5.5) with the blocks of a BIBD\((7, 4, 6t)\) on \(G_1 \cup G_2\) (where \(G_1\) is the first group and \(G_2\) is the second group) and the blocks of a BIBD\((6, 4, 6s – 6t)\) on \(G_2\) give us the blocks of a GDD\((1, 6, 4; \lambda_1 = 6s + 4, \lambda_2 = 6t + 1)\).
We have the following corollary for \(n = 6\) and \(\lambda_1 \geq \lambda_2\).
Corollary 5.9. The necessary conditions (given in Table 1 and Theorem 4.2) are sufficient for the existence of a GDD\((1, 6, 4; \lambda_1, \lambda_2)\) where \(\lambda_1 \geq \lambda_2\). ]
Example 5.10. Suppose \(\lambda_1 \equiv 1 \pmod 2\), \(\lambda_2 \equiv 3 \pmod 6 = 3\lambda\) and \(\lambda_1 \ge \lambda\). Union the first group \(G_1\) with the blocks of a BIBD\((7, 3, \lambda)\) on the second group \(G_2\), and combining the resulting blocks and \(\frac{\lambda_1 – \lambda_2}{2}\) copies of the blocks of BIBD\((7, 4, 2)\) gives us a GDD\((1, 7, 4; \lambda_1 \equiv 1 \pmod 2, \lambda_2 \equiv 3 \pmod 6)\). Using the same construction we can also obtain a GDD\((1, 7, 4; \lambda_1 \equiv 0 \pmod 6, \lambda_2 \equiv 0 \pmod 6)\).
Corollary 5.11. The necessary conditions (given in Table 1 and Theorem 4.2) are sufficient for the existence of a GDD\((1, 7, 4; \lambda_1, \lambda_2)\) where \(\lambda_1 \geq \lambda_2\). ]
One may continue to construct smaller designs as given in this section, but in the next section, we give some general results.
Theorem 6.1. If a GDD\((n_1 = 1, n_2 = n, k;\lambda_1, \lambda_2)\) and a GDD\((n, m, k;\) \(0, \lambda_1)\) exist, a GDD\((n_1 = 1, n_2 = nm, k; \lambda_1, \lambda_2)\) exists.
Proof. Let \(G_1 = \{x\}\) and \(G_2 = \{1, 2, \cdots, nm\}\). Form a partition of \(S_1, \cdots, S_m\) of \(G_2\) into \(m\) groups of size \(n\). Let \(H_i\) be a GDD\((n_1 = 1, n_2 = n, k;\lambda_1, \lambda_2\) on \(G_1\) and \(S_i\), \(i = 1, \cdots, m\). Let \(S\) be a GDD\((n, m, k;0, \lambda_1)\) where \(m\) groups are \(S_1, \cdots, S_m\). The blocks of \(S\) together with the blocks of \(H_i\), \(i = 1, \cdots, m\) give us the blocks of the required GDD\((n_1 = 1, n_2 = nm, k; \lambda_1, \lambda_2)\) on \(G_1\) and \(G_2\). Given any pair of distinct elements from \(G_2\), either both elements are in the same \(S_i\) or they are in different \(S_i\)’s (\(i = 1, \cdots, m\)). Note that any pair of distinct elements in the same \(S_i\) occurs in the blocks of \(H_i\) \(\lambda_1\) times, and any pair of distinct elements from different \(S_i\)’s occurs exactly \(\lambda_1\) times in the blocks of \(S\). A pair \((x, y)\) where \(x \in G_1\) and \(y \in G_2\) occurs \(\lambda_2\) times in \(H_j\) if \(y\) is in \(S_j\) (\(j = 1, \cdots, m\)). ◻
Example 6.2. Since a GDD\((n_1 = 1, n_2 = 7, 4; 1, 3)\) exists and a GDD\((n\) \(= 7, m, 4; 0, 1)\) exists for \(m \equiv 1, 4 \pmod{12}\), a GDD\((n_1 = 1, n_2 = 7m, 4; 1, 3)\) exists for \(m \equiv 1, 4 \pmod{12}\). In particular, a GDD\((n_1 = 1, n_2 = 91, 4; 1, 3)\) exists. Note that \(\lambda_1 < \lambda_2\).
We get an important corollary to Theorem 6.1.
Corollary 6.3. If \(m \equiv 1 \pmod{3}\) and \(\lambda_1\) is even, then a GDD\((n, m, 4;\) \(0, \lambda_1)\) exists. Therefore, as the necessary conditions (given in Table 1 and Theorem 4.2) are sufficient for the existence of a GDD\((n_1 = 1, n_2 = 6, 4; \lambda_1, \lambda_2)\) for any even \(\lambda_1 \geq \lambda_2\) by Corollary 5.9, then the same holds for a GDD\((n_1 = 1, n_2 = 6m, 4; \lambda_1, \lambda_2)\). In particular, the necessary conditions are sufficient for
(i) \(\lambda_2 \equiv 1 \pmod{6}\) and \(\lambda_1 \equiv 4 \pmod{6}\) and \(n \equiv 6 \pmod{36}\);
(ii) \(\lambda_2 \equiv 5 \pmod{6}\) and \(\lambda_1 \equiv 2 \pmod{6}\) and \(n \equiv 6 \pmod{36}\);
Similarly, as the necessary conditions are sufficient for a GDD\((n_1 = 1, n_2 = 7, 4; \lambda_1, \lambda_2)\) for \(\lambda_1 \geq \lambda_2\) by Corollary 5.11, the necessary conditions are sufficient for
(iii) \(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 1, 5 \pmod{6}\) and except for \(n \equiv 7 \pmod{84}\). ]
Using Theorem 1.4 and Theorem 1.8, we have the following Lemmas 6.4 and 6.5.
Lemma 6.4. Necessary conditions (given in Table 1 and Theorem 4.2)are sufficient for the existence of a GDD\((1, n, 4;\lambda_1,\lambda_2)\) where \(\lambda_1 \equiv \lambda_2 \pmod{6}\) and \(\lambda_1 \ge \lambda_2\) (the six cases in the main diagonal in Table 1).
Lemma 6.5. Necessary conditions (given in Table 1 and Theorem 4.2) are sufficient for the existence of a GDD\((1, n, 4;\lambda_1,\lambda_2)\) where \(\lambda_2 \equiv 0 \pmod{6}\) and \(\lambda_1 \ge \lambda_2\) (the first column in Table 1).
For the two cases in the third column in Table 1, note that Lemma 6.4 implies that the necessary conditions are sufficient for the existence of a GDD\((1, n, 4; \lambda_1 = 6s + 2,\lambda_2 = 6t + 2)\) where \(s \geq t\). Next, let \(n = 3t\) where \(t \equiv 0, 3 \pmod{4}\) (i.e. \(n \equiv 0, 9 \pmod{12}\)). The union of the blocks of a BIBD\((3t + 1, 4, 2)\) and the blocks of a BIBD\((3t, 4, 3)\) on \(G_1 \cup G_2\) (both exist by Theorem 1.4 for \(t \equiv 0, 3 \pmod{4}\)) gives us a GDD\((1, 3t, 4; 5, 2)\). The blocks of these blocks combined with the blocks of \(t\) copies a BIBD\((3t + 1, 4, 6)\) and \(s – t\) copies of a BIBD\((3t, 4, 6)\) on \(G_1 \cup G_2\) give us the blocks of a GDD\((1, n, 4;\lambda_1 = 6s + 5,\lambda_2 = 6t + 2)\) where \(s \geq t\). We have the following lemma.
Lemma 6.6. Necessary conditions (given in Table 1 and Theorem 4.2) are sufficient for the existence of a GDD\((1, n, 4;\lambda_1,\lambda_2)\) where \(\lambda_2 \equiv 2 \pmod{6}\) and \(\lambda_1 \ge \lambda_2\) (the third column in Table 1).
In the fifth column of Table 1, let \(\lambda_2 = 6s + 4\), \(\lambda_1 = 6t + 1\) and \(\lambda_1 \ge \lambda_2\) (i.e. \(6(t – s) – 3 \ge 0\)). If \(n \equiv 0, 9 \pmod{12}\), then a BIBD\((n + 1, 4, 6s + 4)\) exists and a BIBD\((n, 4, 6(t – s) – 3)\) exists. By Theorem 1.8, a GDD\((1, n , 4; 6s + 4 + 6(t – s) – 3 = 6t + 1, 6s + 4)\) exists. Therefore, we have the following lemma.
Lemma 6.7. Necessary conditions (given in Table 1 and Theorem 4.2) are sufficient for the existence of a GDD\((1, n, 4;\lambda_1,\lambda_2)\) where \(\lambda_2 \equiv 4 \pmod{6}\) and \(\lambda_1 \ge \lambda_2\) (the fifth column in Table 1).
Similarly, in each of the following cases in Columns 2, 4 and 6 in Table 1, since a BIBD\((n + 1, 4, \lambda_2)\) exists and a BIBD\((n, 4, \lambda_1 – \lambda_2)\) exists, by Theorem 1.8, a GDD\((1, n , 4; \lambda_1,\\ \lambda_2)\) exists where \(\lambda_1 \ge \lambda_2\):
\(\lambda_2 \equiv 1 \pmod{6}\) and \(\lambda_1 \equiv 4 \pmod{6}\) and \(n \equiv 0 \pmod{12}\);
\(\lambda_2 \equiv 5 \pmod{6}\) and \(\lambda_1 \equiv 2 \pmod{6}\) and \(n \equiv 0 \pmod{12}\);
\(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 0 \pmod{6}\) and \(n \equiv 0 \pmod{4}\);
\(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 1, 5 \pmod{6}\) and \(n \equiv 4 \pmod{12}\);
\(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 2, 4 \pmod{6}\) and \(n \equiv 4 \pmod{12}\).
We have the following theorem from the above lemmas and Corollary 6.3.
Theorem 6.8. The necessary conditions are sufficient for the existence of a GDD\((1, n, 4;\\ \lambda_1, \lambda_2)\), where \(\lambda_1 \ge \lambda_2\), except possibly for the following cases:
\(\lambda_2 \equiv 1 \pmod{6}\) and \(\lambda_1 \equiv 4 \pmod{6}\) and \(n \equiv 6 \pmod{12}\) except for \(n \equiv 6 \pmod{36}\);
\(\lambda_2 \equiv 5 \pmod{6}\) and \(\lambda_1 \equiv 2 \pmod{6}\) and \(n \equiv 6 \pmod{12}\) except for \(n \equiv 6 \pmod{36}\);
\(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 0 \pmod{6}\) and \(n \equiv 2 \pmod{4}\);
\(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 1, 5 \pmod{6}\) and \(n \equiv 7 \pmod{12}\) except for \(n \equiv 7 \pmod{84}\);
\(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 2, 4 \pmod{6}\) and \(n \equiv 10 \pmod{12}\).
Recall that Corollary 1.10 gives specific examples for the case \(\lambda_2 \equiv 3 \pmod{6}\) and \(\lambda_1 \equiv 1, 5 \pmod{6}\) and \(n \equiv 7 \pmod{12}\) of Theorem 6.8.
In this paper, we studied GDD\((n_1 = 1, n_2 = n, 4; \lambda_1, \lambda_2)\), and proved the sufficiency of the necessary conditions (given in Table 1 and Theorem 4.2)for the existence of the GDDs for many cases where \(\lambda_1 \geq \lambda_2\). We also had some general results and provided constructions for larger block sizes as well as when the first group size \(n_1\) is not 1 or \(\lambda_1 < \lambda_2\). A natural next step is to complete the open cases listed in Theorem 6.8 and systematically study the existence when \(\lambda_1 < \lambda_2\).