On Constructions of GMGDs

1. Introduction

One of the most studied designs in combinatorial design theory is a balanced incomplete block design:

As given in [1],

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.

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 }_{2}n(m–1)}{k–1}$ (called the replication number) of the $b=\frac{nmr}{k}$ blocks.

As a consequence of the above result, we have

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.

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.

In other words, the points of the $mn$-set are partitioned into $m$ groups $R_1,R_2,\dots ,R_m$ (for rows) and $n$ groups $C_1,C_2,\dots ,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)$.

A very useful construction of a GMGD is given below, for any block size if a MGD exists.

In particular, Assaf [5] proved that the necessary conditions given below were sufficient for block size $k=3$.

From Theorem 3, and Theorem 5 we get,

For example, if ${\lambda }_1\equiv 1(\mathrm{mod}6)$, and ${\lambda }_2\equiv 5(\mathrm{mod}6)$, and $m,n\equiv 1$ or $3(\mathrm{mod}6)$, a GMGD$(3,{\lambda }_1,$ ${\lambda }_2,m,n)$ exists. Another example, ${\lambda }_1=3$, ${\lambda }_2=2$, if $m\equiv 3(\mathrm{mod}6)$ and $n\equiv 1(\mathrm{mod}6)$, a GMGD$(3,3,2,m,n)$ exists.

2. Necessary Conditions For GMGD$\mathbf{(}\mathbf{k}\mathbf{,}{\lambda }_{\mathbf{1}}\mathbf{,}{\lambda }_{\mathbf{2}}\mathbf{,}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{)}$

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

$$\begin{array}{}\text{(1)}& r={\displaystyle \frac{{\lambda }_1(m+n-2)+{\lambda }_2(mn-(m+n-1))}{k-1}.}\end{array}$$ From $vr=bk$, we have $vr=(mn)(\frac{{\lambda }_1(m+n-2)+{\lambda }_2(mn-(m+n-1))}{k-1})=bk$, we have $$\begin{array}{}\text{(2)}& b={\displaystyle \frac{mn({\lambda }_1(m+n-2)+{\lambda }_2(mn-(m+n-1)))}{k(k-1)}.}\end{array}$$ Since $r$ and $b$ must be positive integers, we have the following result.

3. GMGD$\mathbf{(}\mathbf{k}\mathbf{=}\mathbf{3}\mathbf{,}{\lambda }_{\mathbf{1}}\mathbf{,}{\lambda }_{\mathbf{2}}\mathbf{,}\mathbf{m}\mathbf{=}\mathbf{2}\mathbf{,}\mathbf{n}\mathbf{)}$

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\ne 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\ne 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.

$$\begin{array}{}\text{(3)}& x+y+z+w+u+t=b=\frac{mn({\lambda }_1(m+n-2)+{\lambda }_2(mn-(m+n-1)))}{k(k-1)},\end{array}$$ $$\begin{array}{}\text{(4)}& 3x+3y+2z+w+u=\frac{{\lambda }_{1}mn(m+n-2)}{2},\end{array}$$ and $$\begin{array}{}\text{(5)}& z+2w+2u+3t=\frac{{\lambda }_{2}m{n}^2(mn-m–n+1)}{2}.\end{array}$$

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 }_{1}n+{\lambda }_2(n+1))}{6},$$ $$3x+2n+u={\lambda }_1{n}^2,$$ $$n+2u={\lambda }_{2}n(n–1).$$ We have $u=\frac{{\lambda }_{2}n(n–1)–n}{2}$ and $x=\frac{2{\lambda }_1{n}^2–{\lambda }_{2}n(n–1)–3n}{6}$. Since $x$ must be a non-negative integer, we have $$\begin{array}{}\text{(6)}& 2{\lambda }_1{n}^2–{\lambda }_{2}n(n–1)–3n\ge 0,\end{array}$$ and $$\begin{array}{}\text{(7)}& 2{\lambda }_1{n}^2–{\lambda }_{2}n(n–1)–3n\equiv 0(\mathrm{mod}6).\end{array}$$

From Eq. (6), we should include the following as additional necessary condition where $m=2$.

3.1. GMGD$(k=3,{\lambda }_1=1$, ${\lambda }_2=1,m=2,n)$

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(\mathrm{mod}6)$. Since $2n\equiv 0,4(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}6)$ and $m=2$, ${\lambda }_2$ must be an even number.

3.2. GMGD$(k=3,{\lambda }_1,{\lambda }_2=2,m=2,n)$

If ${\lambda }_2=2$, then ${\lambda }_1\ge 2$ by Theorem 7. If ${\lambda }_1=2$, we have $n\equiv 0,2(\mathrm{mod}6)$ from Eq. 7. Since $2n\equiv 0,4(\mathrm{mod}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(\mathrm{mod}6)$ from Eq. 7. The blocks of a GMGD$(3,3,2,2,4)$ are provided below.

The following example is the one noted in the abstract.

3.3. $n$ to $tn$ Construction of a GMGD

To better understand the construction presented in the Theorem 8, first let us see Example 4 below where $t=3$.

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$.

Examples 2 and 3 and Theorem 8 imply Corollary 4 below. Note that when ${\lambda }_2=2$, the condition ${\lambda }_{2}t(t–1)\equiv 0(\mathrm{mod}3)$ in Theorem 8 becomes $t\equiv 0,1(\mathrm{mod}3)$.

Taking $\lambda$ copies of a GMGD$(3,3,2,2,n)$ for $n=4t$ or $6t$, we have the following corollary.

4. GMGD$\mathbf{(}\mathbf{k}\mathbf{=}\mathbf{3}\mathbf{,}{\lambda }_{\mathbf{1}}\mathbf{=}\lambda \mathbf{,}{\lambda }_{\mathbf{2}}\mathbf{=}\mathbf{2}\lambda \mathbf{,}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{)}$

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(\mathrm{mod}2),$$ i.e., $$2mn-m-n\equiv 0(\mathrm{mod}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(\mathrm{mod}6),$$ i.e., $$mn(2mn-m-n)\equiv 0(\mathrm{mod}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.

Here is an important observation.

The above theorem along with Corollary 1 gives us

Taking ${\lambda }_1$ copies of a GMGD$(3,{\lambda }_1=1,{\lambda }_2=2,m,n)$ we have;

In fact, we can generalize this as follows.

5. GMGD$\mathbf{(}\mathbf{k}\mathbf{=}\mathbf{3}\mathbf{,}{\lambda }_{\mathbf{1}}\mathbf{=}\mathbf{2}\mathbf{,}{\lambda }_{\mathbf{2}}\mathbf{=}\mathbf{3}\mathbf{,}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{)}$

We start with an example of a GMGD$(3,2,3,3,4)$.

This example can be generalized to give a construction, which also generalizes Theorem 9.

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$.

We can also apply Theorem 4 to show the existence of a GMGD$(3,2,3,m,n)$ as follows.

Conflict of Interest

The authors declare no conflict of interest.