Menu
We propose and study the problem of finding the smallest nonnegative integer \(s\) such that a GDD\((m, n, 3; 0, \lambda)\) can be embedded into a BIBD\((mn + s, 3, \lambda)\). We find the values of \(s\) for all cases except for the case where \(n \equiv 5 \pmod{6}\) and \(m \equiv 1, 3 \pmod{6}\) and \(m \ge 3\), which remains as an open problem.
Balanced incomplete block designs (BIBDs) and group divisible designs (GDDs) have been studied for their usefulness in statistics and for their universal application to constructions of new designs. Certain difficulties are present especially when the number of groups is smaller than the block size.
Definition 1. A balanced incomplete block design, BIBD\((v, b, r, k, \lambda)\), is a collection of \(b\) \(k\)-subsets \((\)called blocks\()\) of a \(v\)-set \(V\), such that each element appears in exactly \(r\) blocks, every pair of distinct elements of \(V\) occurs in \(\lambda\) blocks and \(k < v.\) A BIBD\((v,b,r,k,\lambda)\) is also written as a BIBD\((v, k, \lambda)\). The parameter \(\lambda\) is called the index of the design.
A BIBD\((v, 3, 1)\) is also called a Steiner Triple System(STS(\(v\))), and it is known that a STS(\(v\)) exists iff \(v \equiv 1, 3 \pmod{6}\). For general \(v\) and \(\lambda\), we have the following.
A BIBD\((v,3,\lambda)\) where \(\lambda \equiv 1,5\pmod 6\) exists if \(v \equiv 1, 3\pmod 6\).
A BIBD\((v,3,\lambda)\) where \(\lambda\equiv 2,4\pmod 6\) exists if \(v \equiv 0, 1\pmod 3\).
A BIBD\((v,3,\lambda)\) where \(\lambda\equiv 3 \pmod 6\) exists if \(v \equiv 1\pmod 2\).
A BIBD\((v,3,\lambda)\) where \(\lambda\equiv 0\pmod 6\) exists if \(v\geq 3\).
Definition 2. A group divisible design, GDD\((m, n, 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 = mn\) elements of \(V\) are partitioned into \(m\) subsets \((\)called groups\()\) of size \(n\) each; 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{mnr}{k}\) blocks; 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.
Example 1. A GDD\((m = 3, n = 2, k = 3;\lambda_1 = 0, \lambda_2 = 3)\) on \(V = \{1, 2, 3, 4, 5, 6\}\) is as follows. Partitioning \(V\) into three groups \(G_1 = \color{red} \{1, 2\}\), \(G_2 = \color{black} \{3, 4\}\) and \(G_3 = \color{green} \{5, 6\}\), and the 12 blocks are \[\begin{array}{ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc} \color{red}1&\color{red}1&\color{red}1&\color{red}1&\color{red}2&\color{red}2&\color{red}2&\color{red}2&\color{red}1&\color{red}1&\color{red}2&\color{red}2\\ \color{black}3&\color{black}3&\color{black}4&\color{black}4&\color{black}3&\color{black}3&\color{black}4&\color{black}4&\color{black}3&\color{black}4&\color{black}3&\color{black}4\\ \color{green}5&\color{green}6&\color{green}5&\color{green}6&\color{green}5&\color{green}6&\color{green}5&\color{green}6&\color{green}5&\color{green}6&\color{green}6&\color{green}5\\ \end{array}\]
Definition 3. A Partial Steiner Triple System on \(v\) points, PSTS\((v)\), is a pair \((V, X)\), where \(V\) denotes a set of \(v\) elements and \(X\) denotes a set of \(b\) triples from \(V\), such that \(|B \cap B'| \le 1\), when \(B, B' \in X\) and \(B \neq B'\).
It is well known that every PSTS\((u)\) has an embedding in an STS\((v)\) for each \(v \equiv 1, 3 \pmod {6}\) satisfying \(v \ge 2u + 1\) [1]. It is also known that this result is best possible in the sense that, for each \(u \ge 9\), there exists an PSTS\((u)\) that does not have an embedding in an STS\((v)\) for any \(v < 2u + 1\). Studies in [3] have shown that some PSTS\((u)\)s do have embeddings in a STS\((v)\) for \(v < 2u + 1\). In this paper, we are studying such an embedding where the partial triple system is a GDD\((m, n, 3; 0, \lambda)\) (where \(u = mn\)). As a GDD structure is more specific, we can reduce the bound on \(v\) significantly and in fact get exact value. For example, when \(\lambda = 1\), if \(n \equiv 1, 3 \pmod {6}\), then \(v = u = mn\); if \(n \equiv 0, 2 \pmod {6}\), then \(v = u + 1 = mn + 1\). The challenge arises when \(n \equiv 5 \pmod {6}\). In other words, we study the problem to find the smallest nonnegative integer \(s\) such that a GDD\((m, n, 3; 0, \lambda)\) can be embedded into a BIBD\((mn + s, 3, \lambda)\) in this paper.
Example 2. This example shows that the blocks of a GDD\((m=3, n=2, k=3;\lambda_1=0, \lambda_2=3)\) is embedded in a BIBD\((v = 7 = m \times n + 1, k = 3, \lambda = \lambda_2 = 3)\), where the smallest nonnegative integer \(s\) is 1. A BIBD\((7, 3, 3)\) on \(V \cup \color{blue} \{a\}\) has 21 blocks where the first 12 blocks are from the GDD\((2, 3, 3;0, 3)\) on \(V = \{1, 2, 3, 4, 5, 6\}\), \(G_1 = \color{red} \{1, 2\}\), \(G_2 = \color{black} \{3, 4\}\) and \(G_3 = \color{green} \{5, 6\}\) in Example 1.
\[\begin{array}{cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc} \color{red}1&\color{red}1&\color{red}1&\color{red}1&\color{red}2&\color{red}2&\color{red}2&\color{red}2&\color{red}1&\color{red}1&\color{red}2&\color{red}2&\color{red}1&\color{red}1&\color{red}1&\color{black}3&\color{black}3&\color{black}3&\color{green}5&\color{green}5&\color{green}5\\ \color{black}3&\color{black}3&\color{black}4&\color{black}4&\color{black}3&\color{black}3&\color{black}4&\color{black}4&\color{black}3&\color{black}4&\color{black}3&\color{black}4&\color{red}2&\color{red}2&\color{red}2&\color{black}4&\color{black}4&\color{black}4&\color{green}6&\color{green}6&\color{green}6\\ \color{green}5&\color{green}6&\color{green}5&\color{green}6&\color{green}5&\color{green}6&\color{green}5&\color{green}6&\color{green}5&\color{green}6&\color{green}6&\color{green}5&\color{blue}a&\color{blue}a&\color{blue}a&\color{blue}a&\color{blue}a&\color{blue}a&\color{blue}a&\color{blue}a&\color{blue}a\\ \end{array}\]
Notice that if a BIBD\((n, k, \lambda)\) exists, then we can combine the blocks of a BIBD\((n, k, \lambda)\) on each of the \(m\) groups with a GDD\((m, n, k; 0, \lambda)\) to have a BIBD\((mn, k, \lambda)\). Hence, we have the following observation.
Observation 1. A GDD\((m, n, k; 0, \lambda)\) can be embedded into a BIBD \((mn, k, \lambda)\) if a BIBD\((n, k, \lambda)\) exists.
Corollary 1. Necessary conditions are sufficient for embedding a GDD\((m, n, 3; 0, \lambda)\) into a BIBD\((mn, 3, \lambda)\) where the smallest \(s\) equals 0 for \(n \equiv 1, 3 \pmod 6\) for any \(\lambda \ge 1\).
Proof. If \(n = 1\), a GDD\((m, 1, 3; 0, \lambda)\) is a BIBD\((m, 3, \lambda)\). For \(n \ge 3\), a BIBD\((n, 3, \lambda)\) exists if \(n \equiv 1, 3 \pmod 6\). By Observation 1, a GDD\((m, n, 3;\) \(0, \lambda)\) can be embedded in a BIBD\((mn, 3, \lambda)\) where the smallest \(s\) equals 0. ◻
Lemma 1. [2] The necessary and sufficient conditions of the existence of a GDD\((m, n, 3; 0, \lambda)\) are \(m \ge 3\), \(\lambda(m – 1)n \equiv 0 \pmod 2\) and \(\lambda m (m – 1)n^2 \equiv 0 \pmod 6\).
Theorem 2. A GDD\((m, n, k;0, \lambda)\) can be embedded into a BIBD\((mn + 1, k, \lambda)\) if a BIBD\((n + 1, k, \lambda)\) exists.
Proof. Combining the blocks of a GDD\((m, n, k;0, \lambda)\), the blocks of a BIBD\((n + 1, k, \lambda)\) on each group \(G_i \cup \{\infty\}\) (\(i = 1, \cdots, m\)) gives us a BIBD\((mn + 1, k, \lambda)\). ◻
Corollary 2. Necessary conditions are sufficient for embedding a GDD\((m, n, 3; 0, \lambda)\) into a BIBD\((mn + 1, 3, \lambda)\) where the smallest \(s\) equals 1 for \(n \equiv 0, 2 \pmod 6\) for any \(\lambda \ge 1\).
If \(\lambda \equiv 0 \pmod 6\), the necessary condition for the existence of a GDD\((m,\) \(n, 3; 0, \lambda)\) by Lemma 1 is \(m \ge 3\).
Lemma 2. The necessary condition \(m \ge 3\) is sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn, 3, \lambda)\) (except for \(n = 2\)) and in a BIBD \((mn + 1, 3, \lambda)\), respectively, where \(\lambda \equiv 0 \pmod 6\).
Proof. If \(n = 1\), a GDD\((m, 1, 3; 0, \lambda)\) is a BIBD\((m, 3, \lambda)\). For \(n \ge 3\), a BIBD\((n, 3, \lambda)\) exists if \(\lambda \equiv 0 \pmod 6\), so a GDD\((m, n, 3; 0, \lambda)\) can be embedded in a BIBD\((mn, 3, \lambda)\) by Observation 1. Therefore, the necessary condition \(m \ge 3\) is sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn, 3, \lambda)\) (except for \(n = 2\)) when \(\lambda \equiv 0 \pmod 6\), i.e., \(s = 0\).
Furthermore, for \(n \ge 2\), combining the blocks of a BIBD\((n + 1, 3, \lambda)\) on elements in \(\{a\} \cup G_i\) (\(i = 1, \cdots, m\) and \(a \notin G_i\)) and the blocks of a GDD\((m, n, 3; 0, \lambda)\) (same idea as illustrated in Example 2), we have a BIBD\((mn + 1, 3, \lambda)\). Specifically, this implies that if \(n = 2\), then \(s = 1\). ◻
If \(\lambda \equiv 3 \pmod 6\), the necessary conditions for the existence of a GDD\((m, n, 3; 0, \lambda)\) by Lemma 1 are
\(n\) is even and \(m \ge 3\).
\(n\) is odd and \(m\) is odd and \(m \ge 3\).
Using the same proof as in Lemma 2 (the second part of the proof), we have the following lemma.
Lemma 3. The necessary conditions, \(n\) is even and \(m \ge 3\) are sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn + 1, 3, \lambda)\) where \(\lambda \equiv 3 \pmod 6\).
Note that since a BIBD\((mn, 3, \lambda)\) does not exist if \(\lambda \equiv 3 \pmod 6\) and \(n\) is even, \(s = 1\). Also, since a BIBD\((n, 3, \lambda)\) exists if \(\lambda \equiv 3 \pmod 6\) and \(n\) is odd, we have the following lemma by Observation 1.
Lemma 4. The necessary conditions, \(n\) is odd and \(m\) is odd and \(m \ge 3\) are sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn, 3, \lambda)\) where \(\lambda \equiv 3 \pmod 6\).
If \(\lambda \equiv 2, 4 \pmod 6\), the necessary conditions for the existence of a GDD\((m, n, 3; 0, \lambda)\) by Lemma 1 are
\(n \equiv 0 \pmod 3\) and \(m \ge 3\).
\(n \equiv 1, 2 \pmod 3\) and \(m \equiv 0, 1 \pmod 3\) and \(m \ge 3\).
By Observation 1, we have the following lemma.
Lemma 5. The necessary conditions, \(n \equiv 0 \pmod 3\) and \(m \ge 3\), or \(n \equiv 1 \pmod 3\) and \(m \equiv 0, 1 \pmod 3\) and \(m \ge 3\) are sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn, 3, \lambda)\) where \(\lambda \equiv 2, 4 \pmod 6\).
Use the same proof as in Lemma 2, we have the following lemma.
Lemma 6. The necessary conditions, \(n \equiv 2 \pmod 3\) and \(m \equiv 0, 1 \pmod 3\) and \(m \ge 3\) are sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn + 1, 3, \lambda)\) where \(\lambda \equiv 2, 4 \pmod 6\).
If \(\lambda \equiv 1, 5 \pmod 6\), the necessary conditions for the existence of a GDD\((m, n, 3; 0, \lambda)\) by Lemma 1 are
For \(n \equiv 0 \pmod 6\), \(m \ge 3\).
For \(n \equiv 2, 4 \pmod 6\), \(m \equiv 0, 1 \pmod 3\) and \(m \ge 3\).
For \(n \equiv 1, 5 \pmod 6\), \(m \equiv 1, 3 \pmod 6\) and \(m \ge 3\).
For \(n \equiv 3 \pmod 6\), \(m\) is odd and \(m \ge 3\).
By Corollary 1, we have the following Lemmas 7 and 8.
Lemma 7. The necessary conditions, \(n \equiv 0 \pmod 6\) and \(m \ge 3\) are sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn + 1, 3, \lambda)\) where \(\lambda \equiv 1, 5 \pmod 6\).
Lemma 8. The necessary conditions, \(n \equiv 2 \pmod 6\), \(m \equiv 0, 1 \pmod 3\) and \(m \ge 3\) are sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn + 1, 3, \lambda)\) where \(\lambda \equiv 1, 5 \pmod 6\).
Lemma 9. A GDD\((m, n, 3; 0, \lambda)\) can be embedded in a BIBD\((mn + 3, 3, \lambda)\) if \(n \equiv 4 \pmod 6\) and \(m \equiv 0, 1 \pmod 3\) and \(m \ge 3\). Furthermore, \(s = 3\) is the smallest nonnegative integer if \(\lambda \equiv 1, 5 \pmod 6\).
Proof. If \(n \equiv 4 \pmod 6\) and \(m \equiv 0, 1 \pmod 3\) and \(m \ge 3\), a GDD\((m, n, 3; 0, \lambda)\) exists. A BIBD\((n + 3, 3, 1)\) exists since \(n + 3 \equiv 1 \pmod 6\). Let \(X\) be the collection of the blocks of a GDD\((m, n, 3; 0, \lambda)\) on \(mn\) elements where each group \(G_i\) (\(i = 1, …, m\)) has group size \(n\). Let \(Y_i\) be the blocks of a BIBD\((n + 3, 3, 1)\) on the elements in \(\{a, b, c\} \cup G_i\) (\(i = 1, …, m\)) where one block is \(\{a, b, c\}\) (this can be done by relabelling the elements). The blocks of \(X\) together with \(\lambda\) copies of \(\bigcup_{i = 1}^m (Y_i \backslash \{a, b, c\})\) and \(\lambda\) copies of \(\{a, b, c\}\) forms a BIBD\((mn + 3, 3, \lambda)\).
Furthermore, if \(\lambda \equiv 1, 5 \pmod 6\), a BIBD\((mn, 3, \lambda)\) does not exist, and a BIBD\((mn + 2, 3, \lambda)\) does not exist, and a GDD\((m, n, 3; 0, \lambda)\) cannot be embedded in a BIBD\((mn + 1, 3, \lambda)\) by Theorem 2 since a BIBD\((n + 1, 3, \lambda)\) does not exist, \(s = 3\) is the smallest nonnegative integer. ◻
Example 3. Figure 1 shows the 35 blocks of a BIBD\((15, 3, 1)\) where a GDD\((3, 4, 3; 0, 1)\) is embedded in the BIBD\((12 + 3, 3, 1)\). \(G_1 = \{1, 2, 3, 4\}\), \(G_2 = \{5, 6, 7, 8\}\), and \(G_3 = \{9, 10, 11, 12\}\). As stated in the proof of Lemma 9, the first 16 blocks are the blocks of a GDD\((3, 4, 3; 0, 1)\), and the next 7 blocks are from a BIBD\((7, 3, 1)\) on \(\{a, b, c\} \cup G_1\). The last 12 blocks are from a BIBD\((7, 3, 1)\) on \(\{a, b, c\} \cup G_2\) and on \(\{a, b, c\} \cup G_3\), respectively, where \(\{a, b, c\}\) is removed since it should only be counted once.
By Corollary 1, we have the following.
Corollary 3. The necessary conditions, \(n \equiv 1 \pmod 6\) and \(m \equiv 1, 3 \pmod 6\) and \(m \ge 3\), or \(n \equiv 3 \pmod 6\), \(m\) is odd and \(m \ge 3\) are sufficient to embed a GDD\((m, n, 3; 0, \lambda)\) in a BIBD\((mn, 3, \lambda)\) where \(\lambda \equiv 1, 5 \pmod 6\).
In this paper we proposed a problem to find the smallest nonnegative integer \(s\) such that a GDD\((m, n, k; 0, \lambda)\) can be embedded into a BIBD\((mn + s, 3, \lambda)\). We found the values of \(s\) for all cases except for the case where \(\lambda \equiv 1, 5 \pmod 6\), \(n \equiv 5 \pmod{6}\), \(m \equiv 1, 3 \pmod{6}\) and \(m \ge 3\), which remains as an open problem. As mentioned earlier, every PSTS\((u)\) has an embedding in an STS\((v)\) for each \(v \equiv 1, 3 \pmod {6}\) satisfying \(v \ge 2u + 1\) [1], hence when \(\lambda \equiv 1, 5 \pmod 6\), \(s \leq mn + 1\) for \(n \equiv 5 \pmod 6\) and \(m \equiv 3 \pmod 6\), and \(s \leq mn + 3\) for \(n \equiv 5 \pmod 6\) and \(m \equiv 1 \pmod 6\). Our guess is in these cases \(s = mn + 1\) and \(s = mn + 3\), respectively.
A summary of finding the smallest nonnegative integer \(s\) such that a GDD\((m, n, 3; 0, \lambda)\) can be embedded into a BIBD\((mn + s, 3, \lambda)\) is in Table 1 as follows.
| \(\lambda\) | \(m, n\) | Necessary Conditions Sufficient? | \(s\) |
| \(0 \pmod{6}\) | \(m \ge 3\) | Yes | \(0\) if \(n = 1\) or \(n \ge 3\) |
| \( \) | \( \) | \( \) | \(1\) if \(n = 2\) |
| \(3 \pmod{6}\) | \(n\) even and \(m \ge 3\) | Yes | \(1\) |
| \( \) | \(m, n\) both odd and \(m \ge 3\) | Yes | 0 |
| \(2, 4 \pmod{6}\) | \(n \equiv 0 \pmod{3}\) and \(m \ge 3\) | Yes | \(0\) |
| \(n\equiv 1 \pmod{3}\) and \(m \equiv 0, 1 \pmod{3}\) and \(m \ge 3\) | Yes | \(0\) | |
| \(n \equiv 2 \pmod{3}\) and \(m \equiv 0, 1 \pmod{3}\) and \(m \ge 3\) | Yes | 1 | |
| \(1, 5 \pmod{6}\) | \(n \equiv 0 \pmod{6}\) and \(m \ge 3\) | Yes | \(1\) |
| \(n\equiv 2 \pmod{6}\) and \(m \equiv 0, 1 \pmod{3}\) and \(m \ge 3\) | Yes | \(1\) | |
| \(n \equiv 4 \pmod{6}\) and \(m \equiv 0, 1 \pmod{3}\) and \(m \ge 3\) | Yes | \(3\) | |
| \(n \equiv 1 \pmod{6}\) and \(m \equiv 1, 3 \pmod{6}\) and \(m \ge 3\) | Yes | 0 | |
| \(n \equiv 3 \pmod{6}\) and \(m\) odd and \(m \ge 3\) | Yes | 0 | |
| \(n \equiv 5 \pmod{6}\) and \(m \equiv 1, 3 \pmod{6}\) and \(m \ge 3\) | Yes | Open |
Dinesh Sarvate wishes to thank Professors Liz Jurisich and Bob Mignone for their continued support through departmental research funding. Li Zhang thanks The Citadel Foundation for its support.
The authors declare no conflict of interest.