Menu
Modified group divisible designs MGD\((k, \lambda, m, n)\) are extensively studied because of an intriguing combinatorial structure that they possess and their applications. In this paper, we present a generalization of MGDs called GMGD\((k, \lambda_1, \lambda_2, m, n)\), and we provide some elementary results and constructions of some special cases of GMGDs. In addition, we show that the necessary conditions are sufficient for the existence of a GMGD\((3, \lambda, 2\lambda, m, n)\) for any positive integer \(\lambda\), and a GMGD\((3, 2, 3, m, n)\). Though not a general result, the construction of a GMGD\((3, 3, 2, 2, 6)\) given in the paper is worth mentioning in the abstract. Along with another example of a GMGD\((3, 3, 2, 2, 4)\), and \(n\) to \(tn\) construction, we have families of GMGD\((3, 3\lambda, 2\lambda, 2, n)\)s for \(n = 4t\) or \(6t\) when \(t \equiv 0, 1 \pmod 3\), for any positive integer \(\lambda\).
One of the most studied designs in combinatorial design theory is a balanced incomplete block design:
Definition 1. A balanced incomplete block designs BIBD\((v, k, \lambda)\) is a pair \((V, B)\) where \(V\) is a \(v\)-set of points and \(B\) is a collection of \(k\)-subsets of \(V\) called blocks such that every pair of distinct elements of \(V\) occurs in exactly \(\lambda\) blocks.
As given in [1],
Theorem 1. The necessary and sufficient conditions for the existence of a BIBD\((v, 3, \lambda)\) are given in Table 1.
| \(\lambda\) | \(v\) |
|---|---|
| \(0\ (\bmod\ 6)\) | all \(v \ne 2\) |
| \(1,5\ (\bmod\ 6)\) | \(1,3\ (\bmod\ 6)\) |
| \(2,4\ (\bmod\ 6)\) | \(0,1\ (\bmod\ 3)\) |
| \(3\ (\bmod\ 6)\) | odd |
BIBDs can be applied to construct another well studied designs called group divisible designs (GDDs). GDDs have many applications, one of which is to construct other designs including BIBDs.
Definition 2. [2] A group divisible design GDD\((n, m, k; \lambda_1, \lambda_2)\), is a collection of \(k\)-element subsets of a \(v\)-set \(V\) called blocks which satisfies the following properties: the \(v = nm\) elements of \(V\) are partitioned into \(m\) subsets (called groups) of size \(n\) each; distinct points within the same group are called first associates of each other and appear together in \(\lambda_1\) blocks; any two points not in the same group are called second associates of each other and appear together in \(\lambda_2\) blocks, where \(\lambda_1\) and \(\lambda_2\) are called indices of the GDD.
Note that in a GDD\((n, m, k; \lambda_1, \lambda_2)\), each point of \(V\) appears in \(r = \frac{\lambda_1(n – 1) + \lambda_2n(m – 1)}{k – 1}\) (called the replication number) of the \(b = \frac{nmr}{k}\) blocks.
Theorem 2. [3] The necessary and sufficient conditions for the existence of a GDD\((n, m, 3;\lambda_1 = 0,\lambda_2 = \lambda)\) are
\(m\ge 3\),
\(\lambda(m-1)n\equiv 0 \pmod 2\), and
\(\lambda m(m-1)n^2 \equiv 0 \pmod 6\).
As a consequence of the above result, we have
Corollary 1. A GDD\((n, m, 3;\lambda_1 = 0,\lambda_2 = 1)\) exists when
| \(m\) | \(n\) |
|---|---|
| \(0\ (\bmod\ 6)\) | Even |
| \(1\ (\bmod\ 6)\) | Any |
| \(2\ (\bmod\ 6)\) | \(0\ (\bmod\ 6)\) |
| \(3\ (\bmod\ 6)\) | Any |
| \(4\ (\bmod\ 6)\) | Even |
| \(5\ (\bmod\ 6)\) | \(0\ (\bmod\ 3)\) |
Though the definition of GDDs include nonzero \(\lambda_1\), the above theorem only gives the existence of GDDs with \(\lambda_1 = 0\) and \(k = 3\). The general existence of GDDs for \(k = 3\) was obtained in [2] and [4].
Assaf [5] generalized the concept of GDDs and defined the modified group divisible designs as follows.
Definition 3. A modified group divisible design MGD\((k,\lambda, m, n)\) is a pair \((V, B)\) where \(V = \{(x_i, y_j) \mid 1 \leq i \leq m, 1 \leq j \leq n \}\) is a set of order \(mn\), and \(B\) is a collection of \(k\)-subsets of \(V\) satisfying the following conditions:
every pair of distinct points \((x_{i_1}, y_{j_1})\) and \((x_{i_2}, y_{j_2})\) is contained in exactly \(\lambda\) blocks when \(i_1 \neq i_2\) and \(j_1 \neq j_2\);
any pair of distinct points \((x_{i_1},y_{j_1})\) and \((x_{i_2},y_{j_2})\) where \(i_1 = i_2\) or \(j_1 = j_2\) is not contained in any block.
MGDs possess an intriguing combinatorial structure and are studied extensively. Also, MGDs have many applications, for example, see Assaf [6], Assaf and Wei [7], Abel and Assaf [8], Danziger and Wang [9], Ling and Colbourn [10], and Ge, Wang and Wei [11]. Similar to the more general definition of GDDs, MGDs can be further generalized and studied. With this motivation, we define generalized modified group divisible designs, GMGDs, as follows.
Definition 4. A generalized modified group divisible design GMGD\((k, \lambda_1, \lambda_2, m, n)\) is a pair \((V, B)\) where \(V = \{(x_i, y_j) \mid 1 \leq i \leq m, 1 \leq j \leq n\}\) is a set of order \(mn\), and \(B\) is a collection of \(k\)-subsets of \(V\) satisfying the following conditions:
every pair of distinct points \((x_{i_1},y_{j_1})\) and \((x_{i_2},y_{j_2})\) is contained in exactly \({\lambda}_2\) blocks when \(i_1 \neq i_2\) and \(j_1 \neq j_2\);
every pair of distinct points \((x_{i_1},y_{j_1})\) and \((x_{i_2},y_{j_2})\) where \(i_1=i_2\) or \(j_1=j_2\) is contained in \({\lambda}_1\) blocks.
The subsets \(\{(x_{i}, y_{j}), 1 \leq i \leq m\}\) where \(\ j=1,2,\ldots,n\) are called the first set of groups (or columns), and the subsets \(\{(x_{i},y_{j}), 1 \leq j \leq n \}\) where \(\ i=1,2,\ldots, m\) are called the second set of groups (or rows).
In other words, the points of the \(mn\)-set are partitioned into \(m\) groups \(R_1,R_2, \ldots, R_m\) (for rows) and \(n\) groups \(C_1,C_2,\ldots, C_n\) (for columns) with \(|R_i \cap C_j| =1\) and if two elements are in the same row or column they occur together in \(\lambda_1\) blocks, and otherwise they occur together in \(\lambda_2\) blocks. Notice that a MGD\((k, \lambda, m, n)\) is a special case of a GMGD\((k, \lambda_1, \lambda_2, m, n)\), i.e., a GMGD\((k, \lambda_1 = 0, \lambda_2 = \lambda, m, n)\).
Remark 1 (Case \(k = 2\)). GMGDs for block size \(k = 2\) are trivial. One can use \(\lambda_1\) pairs of each of the groups to form subsets of size \(2\) and if a pair is not from the same row group or column group, repeat it \(\lambda_2\) times, to get a GMGD\((2, \lambda_1, \lambda_2, m, n )\) for any positive integer \(\lambda_1, \lambda_2, m\) and \(n\).
Example 1. A GMGD\((3,2,1,2,3)\) on \(V =\{1, 2, \cdots, 6\}\) and
| \(C_1\) | C\(_2\) | \(C_3\) | |
| \(R_1:\) | 1 | 3 | 5 |
| \(R_2:\) | 2 | 4 | 6 |
.
The blocks are written in columns below
1 1 3 3 5 5 1 2
2 2 4 4 6 6 3 4
3 4 5 6 1 2 5 6
As \(m = 2 < 3\), a MGD\((3, 1, 2, 3)\) does not exist.
A very useful construction of a GMGD is given below, for any block size if a MGD exists.
Theorem 3. If a MGD\((k,\lambda_2, m, n)\), a BIBD\((m,k, \lambda_1)\) and a BIBD\((n,k,\lambda_1)\) exist, then a GMGD \((k,\lambda_1, \lambda_2, m, n)\) exists.
Proof. The blocks of the MGD\((k,\lambda_2, m, n)\) together with the blocks of the BIBD\((m,k,\lambda_1)\) on each column group, and the blocks of the BIBD\((n,k,\lambda_1)\) on each row group give the required GMGD. ◻
In particular, Assaf [5] proved that the necessary conditions given below were sufficient for block size \(k = 3\).
Theorem 4. The necessary conditions for the existence of a MGD\((k, \lambda, m, n)\) are that \(m, n \ge k,\) \(\lambda(mn + 1 – m – n)\equiv 0 \pmod{k – 1}\) and \(\lambda mn(mn + 1 – m – n) \equiv 0 \pmod {k(k -1)}\).
Theorem 5. A MGD\((3, \lambda, m, n)\) exists whenever a BIBD\((m,3,\lambda)\) or a BIBD\((n,3,\lambda)\) exists.
Proof. The necessary conditions given in Theorem 4 are satisfied by any \((v, \lambda)\) pair from Table 1 given in Theorem 1 for \(v = m\) (or \(v = n\)) when \(k=3\). Instead of showing the proof for each pair \((m,\lambda)\) and similarly for any pair \((n,\lambda)\), we show the calculations just for one pair when \(m\equiv 1\pmod{6}\) and \(\lambda=5\), say \((m=6t+1, \lambda=5)\) where \(t\) is any positive integer.
We want to show that \[\lambda(mn + 1 – m – n)\equiv 0 \pmod{2}\] and \[\lambda mn(mn + 1 – m – n) \equiv 0 \pmod {6}.\]
First, note \(mn + 1 – m – n\)= \((6t+1)n+1-(6t+1)-n\) = \(6nt+n+1-6t-1-n=6(n-1)t\), which is even, and hence \[\lambda(mn + 1 – m – n)\equiv 0 \pmod{2}\] as required.
Second, note \(mn(mn + 1 – m – n)\) =\((6t+1)n(6(n-1)t)\), which is divisible by \(6\), and hence \[\lambda mn(mn + 1 – m – n) \equiv 0 \pmod {6}.\]
As the necessary conditions are sufficient for the existence of the required MGD, we have the result. ◻
From Theorem 3, and Theorem 5 we get,
Corollary 2. A GMGD\((3, \lambda_1, \lambda_2, m, n)\) exists, if a BIBD\((m,3,\lambda_2)\) or a BIBD\((n,3,\lambda_2)\) and a BIBD\((m, 3, \lambda_1)\) and a BIBD\((n,3,\lambda_1)\) exist.
For example, if \(\lambda_1 \equiv 1 \pmod 6\), and \(\lambda_2 \equiv 5 \pmod 6\), and \(m, n \equiv 1\) or \(3 \pmod 6\), a GMGD\((3,\lambda_1,\) \(\lambda_2, m, n)\) exists. Another example, \(\lambda_1=3\), \(\lambda_2=2\), if \(m \equiv 3 \pmod 6\) and \(n \equiv 1 \pmod 6\), a GMGD\((3, 3, 2, m, n)\) exists.
Counting the number of pairs with a fixed point, we have \(\lambda_1(m + n – 2)+\lambda_2(mn – (m + n – 1)) = r(k – 1)\). Hence
\[\label{R}\tag{1} r=\displaystyle\frac{\lambda_1(m+n-2)+\lambda_2(mn-(m+n-1))}{k-1}.\] From \(vr = bk\), we have \(vr = (mn)(\frac{\lambda_1(m+n-2)+\lambda_2(mn-(m+n-1))}{k-1}) = bk\), we have \[\label{B}\tag{2} b=\displaystyle\frac{mn(\lambda_1(m+n-2)+\lambda_2(mn-(m+n-1)))}{k(k-1)}.\] Since \(r\) and \(b\) must be positive integers, we have the following result.
Theorem 6. The necessary conditions for the existence of a GMGD\((k,\lambda_1,\lambda_2, m, n)\) are \(\lambda_1(m + n – 2)+\lambda_2(mn-(m+n-1)) \equiv 0 \pmod {(k – 1)}\) and \(mn(\lambda_1(m+n-2)+\lambda_2(mn-(m+n-1))) \equiv 0 \pmod {k(k-1)}\).
Examining different types of blocks in a GMGD\((3, \lambda_1, \lambda_2, m, n)\), there are six possible types of blocks:
Type I: Blocks are subsets of the row groups. These blocks have \(3\) first associate pairs. Assume there are \(x\) such blocks which provide \(3x\) first associate pairs and \(0\) second associate pairs.
Type II: Blocks are subsets of the column groups. These blocks have \(3\) first associate pairs. Assume there are \(y\) such blocks which provide \(3y\) first associate pairs and \(0\) second associate pairs.
Type III: Blocks contain two elements from a row \(R_i\) and two elements from a column \(C_j\) where one element is from both \(R_i\) and \(C_j\). These blocks have \(2\) first associate pairs and \(1\) second associate pair. Assume there are \(z\) such blocks which provide \(2z\) first associate pairs and \(z\) second associate pairs.
Type IV: Blocks contain only one elements from a row \(R_i\) and two elements from a column \(C_j\) for \(i \neq j\) where no two elements are from the same row. These blocks have \(2\) second associate pairs and \(1\) first associate pair. Assume there are \(w\) such blocks which provide \(w\) first associate pairs and \(2w\) second associate pairs.
Type v: Blocks contain only one elements from a column \(C_j\) and two elements from a row \(R_i\) for \(i \neq j\) where no two elements are from the same column. These blocks have \(2\) second associate pairs and \(1\) first associate pair. Assume there are \(u\) such blocks which provide \(u\) first associate pairs and \(2u\) second associate pairs.
Type VI: Blocks contain three elements where no two elements are from the same row or column. These blocks have \(3\) second associate pairs. Assume there are \(t\) such blocks which provide \(0\) first associate pairs and \(3t\) second associate pairs.
Considering the total number of blocks \(b\), the total number of first associate pairs, and the total number of the second associate pairs in a GMGD\((3, \lambda_1, \lambda_2, m, n)\), we have the following three equations.
\[x + y + z + w + u + t = b = \frac{mn(\lambda_1(m+n-2)+\lambda_2(mn-(m+n-1)))}{k(k-1)}, \label{eq3}\tag{3}\] \[3x + 3y + 2z + w + u = \frac{\lambda_1mn(m+n-2)}{2},\label{eq4}\tag{4}\] and \[z + 2w + 2u + 3t = \frac{\lambda_2mn^2(mn- m – n+1)}{2}. \label{eq5}\tag{5}\]
For the \(m = 2\) case, we first consider an example where a design does not exist, although the necessary conditions in Theorem 6 are satisfied. One can check that the necessary conditions in Theorem 6 are satisfied for a GMGD\((3,\lambda_1 = 1, \lambda_2 = 2, m = 2, n = 6)\), but we show that a design does not exist by counting different types of blocks. Let \(R_1=\{ 1,2,3,4,5,6\}\) and \(R_2 = \{7,8,9,10,11,12 \}\) and \(C_i=\{i, i+6\}, i = 1,2,3,4,5,6\). If a GMGD\((3, 1, 2, 2, 6)\) exists, then \(y = 0\), \(w = 0\), \(t = 0\) and \(z = 6\), and there should be \(36\) first associate pairs and \(60\) second associate pairs packed into blocks of size \(3\). That is, \[3x + 12 + u = 36,\] and \[6+ 2u = 60.\] The solution to the equations is \((x, u) = (-1, 27)\), a contradiction to \(x\) and \(u\) must be non-negative integers. Therefore, a design does not exist. This non-existence shown by counting different types of blocks gives us an additional necessary condition for the existence of a GMGD\((3, \lambda_1, \lambda_2,\) \(m = 2, n)\). From Eqs (3), (4) and (5), respectively, we have the following (in this case, \(y = 0\), \(w = 0\) \(t = 0\) and \(z = n\)):
\[n + x + u = \frac{2n(\lambda_1n+\lambda_2(n+1))}{6},\] \[3x + 2n + u = \lambda_1n^2,\] \[n + 2u = \lambda_2n(n – 1).\] We have \(u = \frac{\lambda_2n(n – 1) – n}{2}\) and \(x = \frac{2\lambda_1n^2 – \lambda_2n(n – 1) – 3n}{6}\). Since \(x\) must be a non-negative integer, we have \[2\lambda_1n^2 – \lambda_2n(n – 1) – 3n \ge 0, \label{eq6}\tag{6}\] and \[2\lambda_1n^2 – \lambda_2n(n – 1) – 3n \equiv 0\pmod 6. \label{eq7}\tag{7}\]
From Eq. (6), we should include the following as additional necessary condition where \(m = 2\).
Theorem 7. An additional necessary condition for the existence of a GMGD\((3, \lambda_1, \lambda_2, 2, n)\) is \(\lambda_1 \ge \frac{\lambda_2(n – 1) + 3}{2n}\).
If \(\lambda_2 = 1\), then \(\lambda_1 \ge 1\) by Theorem 7. First, we start with \(\lambda_1 = 1\). Notice that a GMGD\((3, 1, 1, 2, n)\) is just a BIBD\((2n, 3, 1)\). From Eq. (7), we have \(n \equiv 0, 2 \pmod 6\). Since \(2n \equiv 0, 4 \pmod 6\) and a BIBD\((2n, 3, 1)\) does not exist, a GMGD\((3, 1, 1, 2, n)\) does not exist.
Next, we examine the case GMGD\((3, 2, 1, 2, n)\). From Eq. (7), we have \(n \equiv 0 \pmod 6\). If \(n = 6p\), from Eq. (1), we have \(r = \frac{12t + \lambda_2(12t – 6t – 1)}{2} = \frac{18t – 1}{2}\) which is not an integer. Therefore, a GMGD\((3, 2, 1, 2, n)\) does not exist. In addition, if \(n \equiv 0 \pmod 6\) and \(m = 2\), \(\lambda_2\) must be an even number.
If \(\lambda_2 = 2\), then \(\lambda_1 \ge 2\) by Theorem 7. If \(\lambda_1 = 2\), we have \(n \equiv 0, 2 \pmod 6\) from Eq. 7. Since \(2n \equiv 0, 4 \pmod 6\), a BIBD\((2n, 3, 2)\) exists by Theorem 1. Therefore, a GMGD\((3, 2, 2, 2, n)\) (which is just a BIBD\((2n, 3, 2)\)) exists (unlike the case where \(\lambda_1 = \lambda_2 = 1\)).
For the case where \(\lambda_1 = 3\) and \(\lambda_2 = 2\), we have \(n \equiv 0, 4 \pmod 6\) from Eq. 7. The blocks of a GMGD\((3, 3, 2, 2, 4)\) are provided below.
Example 2. A GMGD\((3, 3, 2, 2, 4)\) on \(V = \{1, 2, \cdots, 8\}\) and
| \(C_1\) | C\(_2\) | \(C_3\) | \(C_4\) | |
| \(R_1:\) | 1 | 2 | 3 | 4 |
| \(R_2:\) | 5 | 6 | 7 | 8 |
The blocks are written in columns below
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 5 | 5 | 6 | 6 | |
| 2 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 | 6 | 6 | 3 | 4 | 7 | 4 | 4 | 4 | 7 | 5 | 6 | 6 | 7 | 7 | |
| 3 | 4 | 5 | 6 | 7 | 6 | 8 | 7 | 8 | 3 | 4 | 5 | 8 | 7 | 8 | 8 | 7 | 5 | 5 | 8 | 7 | 8 | 8 | 8 |
The following example is the one noted in the abstract.
Example 3. A GMGD\((3, 3, 2, 2, 6)\) on \(V = \{1, 2, \cdots, 12\}\) and
| \(C_1\) | C\(_2\) | \(C_3\) | \(C_4\) | \(C_5\) | \(C_6\) | |
| \(R_1:\) | 1 | 2 | 3 | 4 | 5 | 6 |
| \(R_2:\) | 7 | 8 | 9 | 10 | 11 | 12 |
The following blocks (where the blocks are written in columns) combined with blocks from a BIBD\((12, 3, 2)\) where the three blocks \(\{4, 5, 9\}\), \(\{4, 6, 7\}\), and \(\{5, 6, 8\}\) are removed from the 44 blocks of the BIBD\((12, 3, 2)\), and together with the block \(\{4, 5, 6\}\) give the required 56 blocks of a GMGD\((3, 3, 2, 2, 6)\). Note that using appropriate relabeling, the blocks \(\{1, 5, 0\}\), \(\{1, 6, 2\}\), and \(\{5, 6, 10\}\) in the blocks of the BIBD\((12, 3, 2)\) given in [12] give us a BIBD\((12, 3, 2)\) with the required blocks \(\{4, 5, 9\}\), \(\{4, 6, 7\}\), and \(\{5, 6, 8\}\).
| 1 | 1 | 2 | 3 | 7 | 7 | 8 | 9 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 4 | 4 | 5 | 8 | 11 | 10 | 10 | 6 | 5 | 4 | 7 | 9 | 8 |
| 3 | 5 | 6 | 6 | 9 | 12 | 11 | 12 | 7 | 8 | 9 | 10 | 11 | 12 |
To better understand the construction presented in the Theorem 8, first let us see Example 4 below where \(t = 3\).
Example 4. Get a GMGD\((3, \lambda_1, \lambda_2, 2, 3n)\) from a GMGD\((3, \lambda_1, \lambda_2, 2, n)\) where \(\lambda_1 \ge \lambda_2\).
Let \(R_1, \cdots, R_6\) be \(6\) disjoint sets of size \(n\). Construct a GMGD\((3, \lambda_1, \lambda_2, 2, n)\) on groups \(R_1, R_2\); \(R_3, R_4\); and \(R_5, R_6\), respectively. Then construct \(\lambda_2\) copies of eight GDD\((n, 3, 3; 0, 1)\)s where the groups are from each of these blocks \(\{R_1, R_3, R_6\}\), \(\{R_1, R_5, R_4\}\), \(\{R_1, R_4, R_6\}\), \(\{R_1, R_3, R_5\}\), \(\{R_2, R_4, R_6\}\), \(\{R_2, R_3, R_6\}\), \(\{R_2, R_4, R_5\}\), \(\{R_2, R_3, R_5\}\), respectively. Also, construct \(\lambda_1 – \lambda_2\) copies of GDD\((n, 3, 3; 0, 1)\)s on groups \(R_1, R_3, R_5\) and on groups \(R_2, R_4, R_6\). The blocks of these GDDs together with the blocks of the GMGDs provide the blocks of a GMGD\((3, \lambda_1, \lambda_2, 2, 3n)\).
Theorem 8. If a GMGD\((3, \lambda_1, \lambda_2, 2, n)\) exists with \(\lambda_1 \ge \lambda_2\) and \(\lambda_2t(t – 1) \equiv 0 \pmod 3\), then a GMGD\((3, \lambda_1, \lambda_2, 2, tn)\) exists.
Proof. Let \(R_1, R_2, \cdots, R_{2t – 1}, R_{2t}\) be \(2t\) disjoint sets of size \(n\). First, we form a set \(X\) of blocks by constructing \(t\) GMGD\((3, \lambda_1, \lambda_2, 2, n)\)s on groups \(R_{2i – 1}, R_{2i}\) with column groups, say \(C_{1i}, C_{2i}, \cdots,\) \(C_{ni}, i = 1, \cdots, t\). Second, we construct GDD\((2, t, 3; 0, \lambda_2)\)s on groups \(\{R_{2i – 1}, R_{2i}\}, i = 1, \cdots, t\). Next, we form a set \(Y\) of blocks by constructing GDD\((n, 3, 3; 0, 1)\)s on groups of each block of the GDD\((2, t, 3; 0, \lambda_2)\)s as follows. Each block of the GDD\((2, t, 3; 0, \lambda_2)\) has three elements, say \(R_i, R_j, R_k\). So we construct a GDD\((n, 3, 3;0, 1)\) with groups \(R_i, R_j, R_k\). Note that when \(\lambda_2t(t – 1) \equiv 0 \pmod 3\), a GDD\((2, t, 3; 0, \lambda_2)\) exists. Lastly, we form a set \(Z\) of blocks by constructing \(\lambda_1 – \lambda_2\) copies of a GDD\((n, t, 3; 0, 1)\) on groups \(R_1, R_3, \cdots,\) \(R_{2t – 1}\), and also \(\lambda_1 – \lambda_2\) copies of a GDD\((n, t, 3; 0, 1)\) on groups \(R_2, R_4, \cdots, R_{2t}\). The blocks in \(X, Y\) and \(Z\) together give us the blocks for a GMGD\((3, \lambda_1, \lambda_2, 2, tn)\).
Now we do the checking for \(\lambda_1\) and \(\lambda_2\). If two elements are from \(R_{2i}\) (or from \(R_{2i – 1}\)), they occur together \(\lambda_1\) times in the GMGD\((3, \lambda_1, \lambda_2, 2, n)\) on groups \(R_{2i – 1}, R_{2i}\) with column groups, say \(C_{1i}, C_{2i}, \cdots, C_{ni}\).
If two elements are in the same column group, say \(C_{ji}\), they occur together \(\lambda_1\) times in the GMGD on \(R_{2i – 1}, R_{2i}\).
If two elements \(x \in R_{2i -1}\) and \(y \in R_{2i}\), and \(x\) and \(y\) are not in the same column group, then \((x, y)\) occur \(\lambda_2\) times in the GMGD on \(R_{2i – 1}, R_{2i}\).
For \(x \in R_{2i -1}\) and \(y \in R_{2j}\) where \(i \neq j\), since \(R_{2i – 1}\) and \(R_{2j}\) occur in \(\lambda_2\) blocks of GDD\((2, t, 3; 0,\) \(\lambda_2)\) on groups \(\{R_{2i – 1}, R_{2i}\}, i = 1, \cdots, t\). Each of these blocks is used to construct a GDD\((n, 3, 3; 0, 1)\). Therefore, \((x, y)\) occur together in \(\lambda_2\) blocks in the set \(Y\) of blocks.
For \(x \in R_{2i -1}\) and \(y \in R_{2j – 1}\) (\(i \neq j\)), \((x, y)\) occur together in \(\lambda_2\) blocks in the set \(Y\) of blocks using the same argument. Also, they occur in exactly \(\lambda_1 – \lambda_2\) blocks in the set \(Z\) of blocks. Therefore, all together \((x, y)\) occur \(\lambda_1 – \lambda_2 + \lambda_2 = \lambda_1\) times. ◻
Note that it is not necessary to use GDD\((2, t, 3; 0, \lambda_2)\) as in Example 4. We may use GDD\((2, t, 4; 0,\) \(\lambda_2)\) as shown in Example 5 below for \(t = 4\).
Example 5. Get a GMGD\((3, \lambda_1, \lambda_2, 2, 4n)\) from a GMGD\((3, \lambda_1, \lambda_2, 2, n)\) where \(\lambda_1 \ge \lambda_2\) and \(n\) is even.
Let \(R_1, \cdots, R_8\) be \(8\) disjoint sets of size \(n\). Construct a GMGD\((3, \lambda_1, \lambda_2, 2, n)\) on groups \(R_1, R_2\); \(R_3, R_4\); \(R_5, R_6\); and \(R_7, R_8\), respectively. Then construct \(\lambda_2\) copies of six GDD\((n, 4, 3;0, 1)\)s where groups are from each of these blocks \(\{R_1, R_3, R_6, R_8\}\), \(\{R_1, R_5, R_4, R_8\}\), \(\{R_1, R_7, R_4, R_6\}\), \(\{R_3, R_5, R_2, R_8\}\), \(\{R_3, R_7, R_2,\) \(R_6\}\), \(\{R_5, R_7, R_2, R_4\}\), respectively. Also, construct \(\lambda_1 – \frac{\lambda_2}{2}\) copies of GDD\((n, 4, 3; 0, 1)\)s on groups \(R_1, R_3, R_5, R_7\) and on groups \(R_2, R_4, R_6, R_8\). Note that from the necessary conditions for the GDDs, if \(m = 4\) and \(n\) is even, then \(\lambda_2\) is even. The blocks of these GDDs together with the blocks of the GMGDs provide the blocks of a GMGD\((3, \lambda_1, \lambda_2, 2, 4n)\).
Examples 2 and 3 and Theorem 8 imply Corollary 4 below. Note that when \(\lambda_2 = 2\), the condition \(\lambda_2t(t – 1) \equiv 0 \pmod 3\) in Theorem 8 becomes \(t \equiv 0, 1 \pmod 3\).
Corollary 3. A GMGD\((3, 3, 2, 2, 4t)\) and a GMGD\((3, 3, 2, 2, 6t)\) exist for \(t \equiv 0, 1 \pmod 3\).
Taking \(\lambda\) copies of a GMGD\((3, 3, 2, 2, n)\) for \(n = 4t\) or \(6t\), we have the following corollary.
Corollary 4. A GMGD\((3, 3\lambda, 2\lambda, 2, 4t)\) and a GMGD\((3, 3\lambda, 2\lambda, 2, 6t)\) exist for \(t \equiv 0, 1 \pmod 3\), for any positive integer \(\lambda\).
In this section, we study the case where \(\lambda_2 = 2\lambda_1\) and \(k = 3\) and \(m, n \ge 3\). We start with \(\lambda_1 = 1\).
If \(\lambda_1 = 1\) and \(\lambda_2 = 2\), from the necessary conditions in Theorem 6, we need first \[(m + n – 2)+2(mn-(m+n-1)) \equiv 0 \pmod {2} ,\] i.e., \[2mn-m-n \equiv 0 \pmod {2} ,\] which implies \(m\) and \(n\) are of the same parity. Second, we need \[mn((m+n-2)+2(mn-(m+n-1))) \equiv 0 \pmod {6},\] i.e., \[mn(2mn-m-n) \equiv 0 \pmod {6}.\] From this and keeping in mind that \(m\) and \(n\) are of the same parity, we have the necessary conditions given in Table 3.
| \(m\) | \(n\) |
|---|---|
| \(0\ (\bmod\ 6)\) | \(0,2,4\ (\bmod\ 6)\) |
| \(1\ (\bmod\ 6)\) | \(1,3\ (\bmod\ 6)\) |
| \(2\ (\bmod\ 6)\) | \(0\ (\bmod\ 6)\) |
| \(3\ (\bmod\ 6)\) | \(1,3,5\ (\bmod\ 6)\) |
| \(4\ (\bmod\ 6)\) | \(0,4\ (\bmod\ 6)\) |
| \(5\ (\bmod\ 6)\) | \(3\ (\bmod\ 6)\) |
Here is an important observation.
Theorem 9. If a GDD\((n, m, k; 0, \lambda)\) and a GDD\((m, n, k;0, \lambda)\) exists, then a GMGD\((k,\lambda_1 = \lambda, \lambda_2 = 2\lambda, m, n)\) exists.
Proof. From the definition of a GMGD, we know that the required GMGD has \(m\) row groups and \(n\) column groups. The blocks of a GDD\((n, m, k;0, \lambda)\) on these \(m\) row groups together with the blocks of a GDD\((m, n, k;0, \lambda)\) on these \(n\) column groups together give the required GMGD\((k,\lambda_1 = \lambda, \lambda_2 = 2\lambda, m, n)\). ◻
The above theorem along with Corollary 1 gives us
Corollary 5. Necessary conditions are sufficient for the existence of a GMGD\((3,\lambda_1 = 1, \lambda_2 = 2, m, n)\).
Proof. A GMGD\((3,\lambda_1 = 1, \lambda_2 = 2, m, n)\) exists for the values of \(m\) and \(n\) which satisfies both tables given below which are respectively necessary and sufficient conditions for the existence of a GDD\((n, m, 3; 0, \lambda=1)\) and a GDD\((m, n, 3;0, \lambda=1)\) are given in Tables 4 and 5.
| \(m\) | \(n\) |
|---|---|
| \(0\ (\bmod\ 6)\) | Even |
| \(1\ (\bmod\ 6)\) | Any |
| \(2\ (\bmod\ 6)\) | \(0\ (\bmod\ 6)\) |
| \(3\ (\bmod\ 6)\) | Any |
| \(4\ (\bmod\ 6)\) | Even |
| \(5\ (\bmod\ 6)\) | \(0\ (\bmod\ 3)\) |
| \(n\) | \(m\) |
|---|---|
| \(0\ (\bmod\ 6)\) | Even |
| \(1\ (\bmod\ 6)\) | Any |
| \(2\ (\bmod\ 6)\) | \(0\ (\bmod\ 6)\) |
| \(3\ (\bmod\ 6)\) | Any |
| \(4\ (\bmod\ 6)\) | Even |
| \(5\ (\bmod\ 6)\) | \(0\ (\bmod\ 3)\) |
Combining Tables 4 and 5, we get the following values of \(m\) and \(n\) in Table 6 where both a GDD\((n, m, 3; 0, 1)\) and a GDD\((m, n, 3;0, 1)\) exist. Hence a GMGD\((3, \lambda_1 = 1, \lambda_2 = 2, m, n)\) exists.
| \(n\) | \(m\) |
|---|---|
| \(0\ (\bmod\ 6)\) | \(0,2,4\ (\bmod\ 6)\) |
| \(1\ (\bmod\ 6)\) | \(1,3\ (\bmod\ 6)\) |
| \(2\ (\bmod\ 6)\) | \(0\ (\bmod\ 6)\) |
| \(3\ (\bmod\ 6)\) | \(1,3,5\ (\bmod\ 6)\) |
| \(4\ (\bmod\ 6)\) | \(0,4\ (\bmod\ 6)\) |
| \(5\ (\bmod\ 6)\) | \(3\ (\bmod\ 6)\) |
These are precisely the necessary conditions for the existence of a GMGD\((3,\lambda_1 = 1, \lambda_2 = 2, m, n)\). Hence the necessary conditions are sufficient for the existence of a GMGD\((3,\lambda_1 = 1, \lambda_2 = 2, m, n)\). ◻
Taking \(\lambda_1\) copies of a GMGD\((3, \lambda_1 = 1, \lambda_2 = 2, m, n)\) we have;
Corollary 6. A GMGD\((3, \lambda_1, \lambda_2 = 2\lambda_1, m, n)\) exists for the values of \(m\) and \(n\) given in the Table 6.
In fact, we can generalize this as follows.
Theorem 10. Necessary conditions for the existence of a GMGD\((k = 3, \lambda, 2\lambda, m, n)\) in Theorem 6 are equivalent to the necessary and sufficient conditions for the existence of a GDD\((m, n, 3; 0, \lambda)\) and a GDD\((n, m, 3; 0, \lambda)\) in Theorem 2, i.e., \(\lambda(m-1)n\equiv 0 \pmod 2\), and \(\lambda m(m-1)n^2 \equiv 0 \pmod 6\), and \(\lambda(n-1)m \equiv 0 \pmod 2\), and \(\lambda n(n-1)m^2 \equiv 0 \pmod 6\).
Proof. Necessary conditions for the existence of GDDs imply necessary conditions for the existence of a GMGD from Theorem 9. To prove the other way around, we observe that the first necessary condition for the existence of a GMGD\((k = 3, \lambda, 2\lambda, m, n)\) in Theorem 6 (\(\lambda(m + n – 2)+ 2\lambda(mn- m – n + 1) \equiv 0 \pmod 2\)) imply \(\lambda m + \lambda n \equiv 0 \pmod 2\), which implies \(\lambda \equiv 0 \pmod 2\) or \(m \equiv n \pmod 2\). These imply the first necessary condition for both GDDs, i.e., \(\lambda(m-1)n\equiv 0 \pmod 2\) and \(\lambda(n-1)m\equiv 0 \pmod 2\). From the second necessary condition for the existence of a GMGD\((k = 3, \lambda, 2\lambda, m, n)\) in Theorem 6 (\(mn(\lambda(m + n – 2)+ 2\lambda(mn- m – n + 1)) \equiv 0 \pmod 6\)), we have \(\lambda m(m-1)n^2 + \lambda n(n-1)m^2 \equiv 0 \pmod 6\). Our aim is to demonstrate that given \(\lambda \equiv 0 \pmod 2\) or \(m \equiv n \pmod 2\), if \(\lambda m(m-1)n^2 + \lambda n(n-1)m^2 \equiv 0 \pmod 6\) is valid, then \(\lambda m(m-1)n^2 \equiv 0 \pmod 6\) and \(\lambda n(n-1)m^2 \equiv 0 \pmod 6\). To this end, we first notice that if any one of \(\lambda n(n-1)m^2\) or \(\lambda m(m-1)n^2\) is \(0 \pmod 6\), then the second expression is also \(0 \pmod 6\). Now it is an easy exercise to show that for all possible \((m, n)\) pairs, one of the terms is \(0 \pmod 6\). ◻
Corollary 7. As the necessary conditions are sufficient for a GDD\((m, n, 3; 0, \lambda)\), necessary conditions are sufficient for the existence of a GMGD\((3, \lambda, 2\lambda, m, n)\).
Corollary 8. A GMGD\((3, 6t + \lambda, 6t + 2\lambda, m, n)\) exists when the necessary conditions for a GMGD\((3, \lambda, 2\lambda, m, n)\) are satisfied.
Proof. Use the blocks of a BIBD\((mn, 3, 6t)\) and the blocks of a GMGD\((3, \lambda, 2\lambda, m, n)\) to get the blocks of a GMGD\((3, 6t + \lambda, 6t + 2\lambda, m, n)\). ◻
We start with an example of a GMGD\((3, 2, 3, 3, 4)\).
Example 6. \(V = \{1, 2, \cdots, 12\}\) and
| \(C_1\) | C\(_2\) | \(C_3\) | \(C_4\) | |
| \(R_1:\) | 1 | 2 | 3 | 4 |
| \(R_2:\) | 5 | 6 | 7 | 8 |
| \(R_3:\) | 9 | 10 | 11 | 12 |
The blocks of a GDD\((3, 4, 3; 0, 2)\) on the column groups, the blocks of a GDD\((4, 3, 3; 0, 1)\) on the row groups, together with the column groups as blocks, give us a GMGD\((3, 2, 3, 3, 4)\).
This example can be generalized to give a construction, which also generalizes Theorem 9.
Theorem 11. If a GDD\((m, n, 3; 0, \lambda_2)\), a GDD\((n, m, 3; 0, \mu_2)\) and a BIBD\((m, 3, \lambda_2 -\mu_2)\) for \(\lambda_2 > \mu_2\) \((\)or a BIBD\((\)\(n, 3, \mu_2 – \lambda_2)\) for \(\lambda_2 < \mu_2\)\()\) exist, then a GMGD\((3, \lambda_2, \lambda_2+\mu_2, m, n)\) exists for \(m, n \ge 3\).
Proof. Assume \(\lambda_2 > \mu_2\), let \(\{a_i,a_j\}\) and \(\{b_i,b_j\}\) be the elements from two different column groups, so that \(\{a_i,b_i\}\) and \(\{a_j,b_j\}\) are elements from two different row groups. Except the pairs \(\{a_i,a_j\}\) and \(\{b_i,b_j\}\) all other four pairs occur together \(\lambda_2\) times from the blocks of GDD\((m, n, 3; 0, \lambda_2)\). Similarly, except the pairs \(\{a_i,b_i\}\) and \(\{a_j,b_j\}\) all other four pairs occur \(\mu_2\) times in the blocks of GDD\((n, m, 3; 0, \mu_2)\). The blocks of BIBD\((m, 3, \lambda_2 -\mu_2)\) on each of the column groups, contain the pairs \(\{a_i,a_j\}\) and \(\{b_i,b_j\}\) exactly \(\lambda_2 -\mu_2\) times. Hence we see that the pairs from the same row group or column group occur \(\lambda_2\) times and all other pairs occur \(\lambda_2+\mu_2\) times as required. Similarly, if \(\lambda_2 < \mu_2\), use the blocks of a BIBD\((n, 3, \mu_2 – \lambda_2)\) instead. ◻
Remark 2. If \(\lambda_2 = \mu_2\), we have Theorem 9.
Corollary 9. If \(m \equiv 1, 3 \pmod 6\) \((\)resp \(n \equiv 1, 3 \pmod 6)\) and \(n \equiv 0, 4 \pmod 6\) \((\)resp \(m \equiv 0,4 \pmod 6\)\()\), then a GMGD\((3, 2, 3, m, n)\) exists.
Next, we find necessary conditions the existence of a GMGD\((k = 3, \lambda_1 = 2, \lambda_2 = 3, m, n)\). We have \[r=\displaystyle\frac{2(m+n-2)+3(mn-(m+n-1))}{2}\] and \[b=\displaystyle\frac{mn[2(m+n-2)+3(mn-(m+n-1))]}{6}.\]
As \(b\) and \(r\) must be integers, following table gives possible values for \(m\) and \(n\) in modulo \(6\).
| \(m\) | \(n\) |
|---|---|
| \(0\) | \(1,3,5\) |
| \(1\) | \(0,1,3,4\) |
| \(2\) | \(3\) |
| \(3\) | any \(n\) |
| \(4\) | \(1,3\) |
| \(5\) | \(0,3\) |
Corollary 10. If \(m \equiv 3 \pmod 6\) and any \(n\), or \(m \equiv 1 \pmod 6\) and \(n \equiv 0, 1, 3, 4 \pmod 6\), then a GMGD\((3, 2, 3, m, n)\) exists.
Proof. From Theorem 2, a GDD\((m, n, 3; \lambda_1=0, \lambda_2=2)\), and a GDD\((n, m, 3; \mu_1 = 0, \mu_2 = 1)\) exist, respectively, for each of the two cases. From Theorem 1, a BIBD\((m, 3, 1)\) exists for \(m \equiv 1, 3 \pmod 6\). Therefore, a GMGD\((3, 2, 3, m, n)\) exists from Theorem 11. ◻
We can also apply Theorem 4 to show the existence of a GMGD\((3, 2, 3, m, n)\) as follows.
Theorem 12. A GMGD\((3, 2, 3, m, n)\) exists if the values of \(m\) and \(n\) satisfy Table 6.
Proof. The necessary and sufficient conditions for the existence of a MGD\((3, \lambda, m, n)\) for \(m, n \ge 3\) in Theorem 4 are \(\lambda(mn + 1 – m – n)\equiv 0 \pmod 2\) and \(\lambda mn(mn + 1 – m – n) \equiv 0 \pmod 6\). For each of the six cases in the table above, a MGD\((3, 1, m, n)\) exists as the necessary conditions are satisfied. We also note that a BIBD\((mn, 3, 2)\) exists from Theorem 1. The blocks of a BIBD\((mn, 3, 2)\) on \(mn\) elements together with the blocks of a MGD\((3, 1, m, n)\) give the required GMGD. ◻
The authors declare no conflict of interest.