3-Group Divisible Designs with 3 Groups and Block Size 5
Abstract
A 3-GDD (n, 2, k, λ1, λ2) was defined by combining the definitions of a group divisible design and a t-design. In this paper, we extend the definitions to 3 groups and block size 5, and we denote such GDD by 3-GDD (n, 3, 5, μ1, μ2). Some necessary conditions for the existence of these GDDs are developed, and several new constructions and specific instances of nonexistence are given.
1. Introduction
A group divisible design, GDD (n, m, k, λ1, λ2), is an ordered triple (, , ), where is a mn-set of symbols, is a partition of into m sets called groups of size n each, and is a collection of k-subsets called blocks of , such that each pair of symbols from the same group occurs in exactly λ1 blocks and each pair of symbols from different groups occurs in exactly λ2 blocks [1–5]. Any two symbols occurring together in the same group are called first associates, and pairs of symbols occurring in different groups are called second associates.
Group divisible designs (GDDs) have been studied for their usefulness in statistics, coding and for their universal application to constructions of new designs (for instance balanced incomplete design, orthogonal arrays, and transversal designs etc.) [6–8]. The existence of such GDDs has been of interest over the years, going back to at least the work of Bose and Shimamoto in 1952 that began classifying such designs [9]. GDDs and t-designs have been studied by many authors [10–13] and the references therein. Recently, a 3-GDD (n, 2, k, λ1, λ2) was defined by extending the definitions of a group divisible designs and a t-design, and some necessary conditions for its existence were given [14, 15].
In this paper, these recent works are extended to include more than two groups. We mainly continue to focus on the definition of 3-GDDs, and we explicitly consider the case when the required designs have three groups of size n each and block size 5. Throughout this paper, such GDD is denoted by 3-GDD (n, 3, 5, μ1, μ2). In this work, some necessary conditions for the existence of such GDDs are determined, the existence of some GDDs will be proved and their constructions are produced. Furthermore, several specific instances of nonexistence are proved.
This work is organized as follows. In Section 2, we present some well-known definitions and examples that will be used to proof the main results. In Section 3, some necessary conditions for the existence of such designs together with their proofs are given. In Section 4, the proofs of some constructions especially when μ2 = 0 are presented. Finally, in Section 5, an infinite families of existences for the 3-GDD when n = 3 are given.
2. Preliminaries
In this section, we present some well-known definitions and concepts which will be used in the subsequent sections.
Definition 1 (see [14].)A t-(v, k, λ) design, or a t-design is a pair , where is a v-set of points and is a collection of k-subsets (blocks) of with the property that every t-subset of is contained in exactly λ blocks. The parameter λ is called the index of the design.
A necessary condition for the existence of a t-(v, k, λ) design is known [13] to be the following equation:
The problem of determining the values of k, t, and for which this condition is also sufficient is not yet solved completely, and less is known about configurations with t = 3.
Example 1. A 3-(8,4,1) design on the set = {1,2, …, 8} is given by the blocks: {1,2,5,6}, {3,4,7,8}, {1,3,5,7}, {2,4,6,8}, {1,4,5,8}, {2,3,6,7}, {1,2,3,4}, {5,6,7,8}, {1,2,7,8}, {3,4,5,6}, {1,3,6,8}, {2,4,5,7}, {1,4,6,7} and {2,3,5,8}.
The concepts of a GDD and a 3-design can be merged to define a 3-GDD as follows.
Definition 2. A 3′-GDD (n, m, k, Λ1, Λ2), for m > 2, is a set of mn symbols partitioned into m parts of size n called groups together with a collection of k-subsets of called blocks, such that
- (i)
Every 3-subset of each group occurs in Λ1 blocks
- (ii)
Every mixed 3-subset, meaning either two symbols are from one group and one symbol from the other group or all three symbols are from different groups, occurs in Λ2 blocks
The above mentioned definition was given in [14, 15], in which case a 3-subset of has only two choices, all symbols from one of the two groups or one symbol from a group and two symbols from the other group. Such GDD was denoted by a 3-GDD (n, 2, 4, λ1, λ2).
Lemma 3 (see [14].)If a 3-(2n, 4, λ2) and a 3-(2n, 4, λ1 − λ2) exists, then a 3-GDD (n, 2, 4, λ1, λ2) exists.
Example 2. Here, = {1,2,3, a, b, c}, G1 = {1,2,3} and G2 = {a, b, c}, the blocks of a 3-GDD (3,2,4,3,1) are: {1,2,3, a}, {1,2,3, b}, {1,2,3, c}, {a, b, c, 1}, {a, b, c, 2} and {a, b, c, 3}.
Following necessary conditions (Table 1, where the values of λ1 and λ2 are given modulo 6) and the existence results of a 3-GDD (n, 2,4, λ1, λ2) are given in [14, 15].
λ1/λ2 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | All n | n even | All n | n even | All n | n even |
1 | 2,4 (mod 6) | 1,2,4,5 (mod 6) | 2,4 (mod 6) | 1,2,4,5 (mod 6) | 2,4 (mod 6) | 1,2,4,5 (mod 6) |
2 | 1,2,4,5 (mod 6) | 2,4 (mod 6) | 1,2,4,5 (mod 6) | 2,4 (mod 6) | 1,2,4,5 (mod 6) | 2,4 (mod 6) |
3 | n even | All n | n even | All n | n even | All n |
4 | 1,2,4,5 (mod 6) | 2,4 (mod 6) | 1,2,4,5 (mod 6) | 2,4 (mod 6) | 1,2,4,5 (mod 6) | 2,4 (mod 6) |
5 | 2,4 (mod 6) | 1,2,4,5 (mod 6) | 2,4 (mod 6) | 1,2,4,5 (mod 6) | 2,4 (mod 6) | 1,2,4,5 (mod 6) |
One may relax condition (ii) in Definition 2 to define a 3-PBIBD as follows.
Definition 4. A 3-PBIBD (partially balanced incomplete block design), 3-PBIBD (n, m, k, θ1, θ2, θ3) is a collection of k-subsets of an mn set , where is partitioned in to m groups of order n such that
- (i)
Every triple formed from symbols of only a single group occurs in θ1 blocks
- (ii)
Every triple formed from symbols of only two groups occurs in θ2 blocks
- (iii)
Every triple formed from symbols of all three groups occurs in θ3 blocks
Definition 5. A 3-GDD (n, m, k, μ1, μ2) is a pair (, ), where is a set of mn elements partitioned into mn-subsets (groups) and is a collection of k-subsets (blocks) of such that
- (i)
Every triple occurs in exactly μ1 blocks if it contains elements from at most 2 groups
- (ii)
It occurs in exactly μ2 blocks if it has all three elements from different groups
Definition 5 is the subject matter of this paper and we explicitly consider the case in which m = 3 and k = 5. Such GDD is denoted by 3-GDD (n, 3, 5, μ1, μ2).
Remark 6. A 3-GDD (n, 3, 5, μ1, μ2) is a 3-PBIBD (n, 3, 5, θ1, θ2, θ3), where θ1 = θ2, denoted by μ1, while θ3 is denoted by μ2.
When μ1 = μ2, a 3-GDD (n, 3, 5, μ1, μ2) is actually a 3-(3n, 5, μ1). It follows that a 3-GDD (n, 3, 5, μ1, μ2) exists if and only if a 3-(3n, 5, μ1) exists.
The next three sections of this paper discuss our research findings.
3. Necessary Conditions
In this section, assuming a 3-GDD (n, 3, 5, μ1, μ2) exists, we obtain some necessary conditions for the existence of a 3-GDD (n, 3, 5, μ1, μ2).
Let λ1 (first associate pair) denote the number of blocks containing {x1, x2}, where x1 and x2 are from the same group, λ2 (second associate pair) denote the number of blocks containing {x, y} where x and y are from different groups, r and b, respectively, denote the replication number and the number of blocks in a 3-GDD.
Theorem 7. Given a 3-GDD (n, 3,5, μ1, μ2),
Proof. The abovementioned results can be proved as follows:
- (1)
We count the number of triples containing a fixed element x in the design in two ways.
-
First, given an element x, it appears in triples of the type (3, 0) and in 2n(n − 1) + 2 triples of the type (2,1) (there are 2n(n − 1) triples of the type (2,1) where x and an element from the same group as x appear with an element of another group, and there are 2 triples of type (2,1) where x appears with two elements from another group). So, in sum, x is in μ1 triples of the form (3,0) or (2,1) in the design.
-
Similarly, there are n2 triples of the type (1,1,1) containing x, and are repeated μ2 times.
-
All together, there are μ1 + n2μ2 triples containing x.
-
Second, in every block containing x, there are 6 triples containing x and x occurs in r blocks, which means there are 6r triples containing x in the design.
-
Hence, 6r = μ1 + n2μ2, and r = ((n − 1)(7n − 2)μ1 + 2n2μ2)/12
- (2)
Again, counting in two ways, in a design with block size 5 and b blocks, there are = 10b triples. On the other hand, there must be exactly triples of type (3,0), 3n2(n − 1)μ1 triples of type (2,1), and n3μ2 triples of type (1,1,1) in the design.
-
Therefore, 10b = + 3n2(n − 1)μ1 + n3μ2 gives equation (3).
- (3)
Let (x1, x2) be a first associate pair and occurs in λ1 blocks. The triples containing (x1, x2) can only be of type (3,0) or (2, 1). There are (n − 2) triples of the type (3,0) and 2n triples of the type (2,1) containing (x1, x2). Now, since these triples occur μ1 times and since the block containing a first associate pair, say (x1, x2) contains three triples containing (x1, x2), we have: λ1 = ((3n − 2)/3)μ1.
- (4)
Let (x, y) be a second associate pair. This pair occurs in triples of the type (2,1) and (1, 1, 1) only. It occurs in 2(n − 1)μ1 triples of type (2,1) and nμ2 triples of type (1, 1, 1).
Each of the λ2 blocks containing the pair (x, y) has three triples containing (x, y).
Hence, 3λ2 = 2(n − 1)μ1 + nμ2 and λ2 = (2(n − 1)μ1 + nμ2)/3.
As a consequence of Theorem 7, we have the following corollaries.
Corollary 8. For μ1 ≡ 0(mod 3), a 3-GDD (n, 3, 5, μ1, μ2) does not exist.
Corollary 9. In a 3-GDD (n, 3, 5, μ1, μ2), λ1 ≠ 0.
Proof. As the number of groups is less than the block size, μ1 ≠ 0. Again from (3) in Theorem 7, λ1 is a multiple of μ1, and hence λ1 ≠ 0
From the original necessary conditions in Theorem 7, when μ1 = μ2 = λ, we get 3-(3n, 5, λ), and from (4) and (5), we must have λ ≡ 0(mod 3). In addition, from (2) and (3) in Theorem 7, the following result follows.
Corollary 10. The necessary conditions for the existence of 3-(3n, 5, λ) are satisfied only under the following cases:
- (i)
If n ≡ 2, 7, 10, 14, 15(mod 20), then λ ≡ 0(mod 3)
- (ii)
If n ≡ 0, 4, 5, 9, 12, 17(mod 20), then λ ≡ 0(mod 6)
- (iii)
If n ≡ 3, 6, 11, 18(mod 20), then λ ≡ 0(mod 15)
- (iv)
If n ≡ 1, 8, 13, 16(mod 20), then λ ≡ 0(mod 30)
Theorem 11. Given a 3-GDD (n, 3, 5, μ1, μ2),
- (i)
μ2 < 3μ1
- (ii)
b ≥ (3n2(n − 1)μ1 + n3μ2)/15
Proof.
- (i)
In a 3-GDD (n, 3, 5, μ1, μ2), triples of the type (1,1,1) occur in the blocks of type (3,1,1) and (2,2,1) only. In each of these blocks which can have a (1,1,1) triples, the number of (2,1) triples are more than the number of (1,1,1) triples.
-
Hence, 3n2(n − 1)μ1 > n3μ2, implies μ2 < 3(n − 1)μ2/n < 3μ1.
- (ii)
We calculated the value of b = (n/20)((n − 1)(7n − 2)μ1 + 2n2μ2) in Theorem 7, if we do not include the triples of the form (3, 0), in the calculations, we obtain the following equation:
(6)
Theorem 12. For n ≤ 5, a 3-GDD (n, 3, 5, μ1, 0) does not exist.
Proof. As μ2 = 0, blocks are of configuration (5,0), (4,1) and (3,2) only. The maximum number of (2,1) triples occur in (3,2) configuration blocks and ratio is 9 : 1 (in each block of configuration (3,2), there are nine (2,1) and one (3,0) triples). Counting the number of (2,1) triples (3n2(n − 1)μ1) and the number of (3,0) triples (n(n − 1)(n − 2)/2), their ratio must be less than or equal to 9.
Thus, 3n2(n − 1)μ1/n(n − 1)(n − 2)/2 ≤ 9⇒6n/n − 2 ≤ 9, which gives n ≥ 6.
From (4) and (5) in Theorem 7, the necessary conditions are satisfied under the following conditions.
Lemma 13. In regards to
- (i)
λ1, for every n, μ1 ≡ 0(mod 3) and μ2 is free
- (ii)
λ2, when
- (i)
n ≡ 0(mod 3), μ1 ≡ 0(mod 3) and μ2 is free
- (ii)
n ≡ 1(mod 3), μ1 is and μ2 ≡ 0(mod 3)
- (iii)
n ≡ 2(mod 3), μ1 + μ2 ≡ 0(mod 3)
- (i)
As the values of b and r must also be integers, Table 2 is a table of congruence restrictions for a 3-GDDs with 3 groups and block size 5 (all values are considered to be in terms of (mod 60) unless otherwise stated).
where
- (i)
⋏1 = 4μ1 + μ2 ≡ 0(mod 5), ⋏2 = μ1 + μ2 ≡ 0(mod 10), ⋏3 = 9μ1 + μ2 ≡ 0(mod 10), ⋏4 = 4μ1 + μ2 ≡ 0(mod 10), ⋏5 = 5μ1 + μ2 ≡ 0(mod 10), ⋏6 = 8μ1 + 3μ2 ≡ 0(mod 10), ⋏7 = μ1 + μ2 ≡ 0(mod 2), and ⋏8 = μ1 + μ2 ≡ 0(mod 5)
- (ii)
∗1 = 5μ1 + 3μ2 ≡ 0(mod 6), ∗2 = 3μ1 + 2μ2 ≡ 0(mod 6), ∗3 = 3μ1 + μ2 ≡ 0(mod 6), and ∗4 = 2μ1 + 3μ2 ≡ 0(mod 6).
r | r | b | b | |
---|---|---|---|---|
n | μ1 | μ2 | μ1 | μ2 |
0 | 0 (mod 6) | All | All | All |
1, 41 | All | 0 (mod 6) | All | 0 (mod 10) |
2, 14, 22, 34, 42, 54 | All | 0 (mod 3) | ⋏1 | ⋏1 |
3 | ∗1 | ∗1 | ⋏2 | ⋏2 |
4, 32, 44, 52 | ∗2 | ∗2 | ⋏1 | ⋏1 |
5, 25 | All | 0 (mod 6) | All | 0 (mod 2) |
6 | 0 (mod 3) | All | All | 0 (mod 5) |
7, 19, 47, 59 | ∗3 | ∗3 | ⋏3 | ⋏3 |
8 | ∗2 | ∗2 | ⋏8 | ⋏8 |
9, 57 | ∗4 | ∗4 | ⋏4 | ⋏4 |
10, 50 | All | 0 (mod 3) | All | All |
11, 31 | ∗3 | ∗3 | ⋏5 | ⋏5 |
12, 24 | 0 (mod 6) | All | ⋏1 | ⋏1 |
13, 53 | All | 0 (mod 6) | ⋏6 | ⋏6 |
15 | ∗1 | ∗1 | ⋏7 | ⋏7 |
16, 56 | ∗2 | ∗2 | All | 0 (mod 5) |
17, 29, 37, 49 | All | 0 (mod 6) | ⋏4 | ⋏4 |
18 | 0 (mod 3) | All | ⋏8 | ⋏8 |
20, 40 | ∗2 | ∗2 | All | All |
21 | ∗4 | ∗4 | All | 0 (mod 10) |
23, 43 | ∗3 | ∗3 | ⋏2 | ⋏2 |
26, 46 | All | 0 (mod 3) | All | 0 (mod 5) |
27, 39 | ∗1 | ∗1 | ⋏3 | ⋏3 |
28 | ∗2 | ∗2 | ⋏7 | ⋏7 |
30 | 0 (mod 3) | All | All | All |
33 | ∗4 | ∗4 | ⋏6 | ⋏6 |
35, 55 | ∗3 | ∗3 | ⋏7 | ⋏7 |
36 | 0 (mod 6) | All | All | 0 (mod 5) |
38, 58 | All | 0 (mod 3) | ⋏8 | ⋏8 |
45 | ∗4 | ∗4 | All | 0 (mod 2) |
48 | 0 (mod 6) | All | ⋏7 | ⋏7 |
51 | ∗1 | ∗1 | ⋏5 | ⋏5 |
b, r, λ1, and λ2 must be positive integers for a design to exist. From Lemma 13 and Table 2, we have more compact necessary conditions for different values of n as follows.
Lemma 14. For
- (i)
n ≡ 0(mod 10), μ1 and μ2 are free in regards to the number of blocks b
- (ii)
n ≡ 0(mod 3) and μ1 ≡ 0(mod 3), λ1&λ2 are integers for any chosen μ2
- (iii)
n ≡ 1,2(mod 3), μ1 ≡ 0(mod 3) and μ2 ≡ 0(mod 3), λ1 & λ2 are integers
- (iv)
n ≡ 1,5(mod 12) and μ2 ≡ 0(mod 6) or n ≡ 2,10(mod 12) and μ2 ≡ 0(mod 3), r is an integer for any chosen μ1
- (v)
n ≡ 1,2,4,7,10(mod 12) and n ≡ 5,17,41,53(mod 60), μ2 is multiple of 3
- (vi)
n ≡ 6(mod 10) and n ≡ 1(mod 20), μ2 is multiple of 5
4. Some Constructions When μ2 = 0
In this section, the proofs of some constructions when μ2 = 0 are given.
Theorem 15.
- (a)
All blocks of a design are of type (3,2) constitute a 3-PBIBD (n, 3, 5, n(n − 1), 3(n − 1)(n − 2)/2, 0), where the number of blocks of such design is
- (b)
There exists a 3-PBIBD (n, 3, 5, (n − 3)(n − 4)/2, 0, 0)
Proof.
- (a)
When all blocks are of type (3,2), the number of blocks of such design is , where gives the number of 3-subsets of 3 groups and gives the number of 2-subsets for each choice of a 3-subset. This also tells the number of blocks containing every (3,0) triple is = n(n − 1).
-
Similarly, let {a, b, x} be (2,1) triple, where the pair {a, b} is from say G1 and the element x is from G2. There are (n − 2)(n − 1) triples containing {a, b, x} (one element each from G1 and G2) or there are triples containing {a, b, x} (3-subsets of G2), and hence in total there are 3(n − 1)(n − 2)/2 blocks of size five containing {a, b, x}.
- (b)
When all blocks are of type (5,0), the number of blocks containing every (3,0) triple is = (n − 3)(n − 4)/2.
Example 3. A 3-GDD (6, 3, 5, 30, 0) exists.
In Theorem 15 (a), if n = 6, then, θ1 = θ2 = n(n − 1) = 3(n − 1)(n − 2)/2 = 30.
Blocks are of type (4, 1) if there are four elements from a single group and one element from other group.
Theorem 16. If all the blocks are of type (4,1), then a 3-GDD (n, 3, 5, μ1, 0) does not exist.
Proof. when all blocks are of type (4,1), a fixed (3,0) triple occurs in 2n(n − 3) and a fixed (2,1) triple occurs in blocks.
Hence, 2n(n − 3) = , which is true only for 3n = −2, which is impossible.
In Theorem 12, a 3-GDD (n, 3, 5, μ1, 0) does not exist when n ≤ 5. But, when n ≥ 6, a 3-GDD (n, 3, 5, μ1, 0) exists for some μ1.
Theorem 17. For n ≥ 6, a 3-GDD (n, 3, 5, 3(n − 1)(n − 2)(n − 3)(n − 4)/4, 0) exists.
Proof. When n ≥ 6, taking = (n − 3)(n − 4)/2 copies of the blocks of Theorem 15(a) together with 3(n − 1)(n − 2)/2 − n(n − 1) = (n − 1)(n − 6)/2 copies of the blocks of Theorem 15(b) give the blocks of 3-GDD (n, 3, 5, 3(n − 1)(n − 2)(n − 3)(n − 4)/4, 0).
Example 4. By Theorem 17, the following 3-GDDs exist:
-
3-GDD (6, 3, 5, 90, 0), 3-GDD (7, 3, 5, 270, 0), 3-GDD (8, 3, 5, 630, 0)
-
3-GDD (9, 3, 5, 1260, 0), 3-GDD (10, 3, 5, 2268, 0), 3-GDD (11, 3, 5, 3780, 0)
-
3-GDD (12, 3, 5, 5940, 0), etc.
Theorem 18. There exists a 3-GDD (n, 3, 5, (n − 1)(n − 2)(n − 3)(n − 4)/4, 0) for n ≥ 6 and n ≡ 2(mod 3).
Proof. If n ≡ 2(mod 3) and n ≥ 6, then both (n − 1)(n − 6)/2 and (n − 3)(n − 4)/2 are divisible by 3. Joining (n − 3)(n − 4)/6 copies of the blocks of Theorem 15(a) together with (n − 1)(n − 6)/6 copies of the blocks of Theorem 15(b) give the blocks of 3-GDD (n, 3, 5, (n − 1)(n − 2)(n − 3)(n − 4)/4, 0).
Example 5. By Theorem 18 above, the following 3-GDDs exist:
-
3-GDD (6, 3, 5, 30, 0), 3-GDD (7, 3, 5, 90, 0), 3-GDD (9, 3, 5, 420, 0)
-
3-GDD (10, 3, 5, 756, 0), 3-GDD (12, 3, 5, 1980, 0), 3-GDD (13, 3, 5, 2970, 0)
-
3-GDD (15, 3, 5, 6006, 0), etc.
5. 3-GDD (3, 3, 5, μ1, μ2)
In this section, we give some families of existences along with several examples of the 3-GDD when n = 3. In addition, some relationship between 3′-GDD (n, m, k, Λ1, Λ2)(Definition 2) and 3-PBIBD (n, m, k, θ1, θ2, θ3) (Definition 4) is designed. We begin with the following three examples (Examples 1–3) of a 3-PBIBD (3, 3, 5, θ1, θ2, θ3).
Example 6. A 3-PBIBD (3, 3, 5, 0, 3, 4) with G1 = {1,2,3}, G2 = {a, b, c}, G3 = {x, y, z} exists and the blocks (written vertically) of this design are as follows.
Example 7. A 3-PBIBD (3, 3, 5, 6, 3, 0) exists and the blocks of this design are obtained by union of every Gi with every two element set of Gj for i ≠ j, where i, j = 1, 2, 3.
Example 8. 3-PBIBD (3, 3, 5, 9, 3, 3) exists. Its blocks are obtained by union of every group with each singleton set of both remaining groups.
Remark 19. When n = 3, from the original necessary conditions in Theorem 7; r, b, λ1 and λ2, respectively, are integers if ∗1: μ1 +3 μ2 ≡ (mod 6), ∗2: μ1 + μ2 ≡ (mod 10), μ1 ≡ 0 (mod 3), and μ1 ≡ 0 (mod 3).
Thus, the values of μ1 and μ1 satisfying the necessary conditions are as follows: μ1 ≡ 0(mod 3)∩∗1∩∗2 and μ2 ≡ ∗1∩∗2.
For n = 3, taking all the possible combinations, the original necessary conditions are satisfied when
- (1)
μ1 ≡ 3(mod 30) and μ2 ≡ 7(mod 10)
- (2)
μ1 ≡ 9(mod 30) and μ2 ≡ 1(mod 10)
- (3)
μ1 ≡ 15(mod 30) and μ2 ≡ 5(mod 10)
- (4)
μ1 ≡ 21(mod 30) and μ2 ≡ 9(mod 10)
- (5)
μ1 ≡ 27(mod 30) and μ2 ≡ 3(mod 10)
- (6)
μ1 ≡ 0(mod 30) and μ2 ≡ 0(mod 10)
- (7)
μ1 ≡ 6(mod 30) and μ2 ≡ 4(mod 10)
- (8)
μ1 ≡ 12(mod 30) and μ2 ≡ 8(mod 10)
- (9)
μ1 ≡ 18(mod 30) and μ2 ≡ 2(mod 10)
- (10)
μ1 ≡ 24(mod 30) and μ2 ≡ 6(mod 10)
Example 9. 3-GDD (3, 3, 5, 9, 11) exists and its blocks are obtained by combining the blocks of Example 3 with two copies of the blocks of Example 6.
Example 10. 3-GDD (3, 3, 5, 6, 4) exists and its blocks are obtained by joining blocks of Examples 6 and 7.
Hence, we have 3-GDD (3, 3, 5, 6t, 4t), for t ≥ 1.
Theorem 20. There exists a 3-GDD (3, 3, 5, 9q + 3p, 11q − 3p) for p ≤ q.
Proof. Blocks of the design are obtained by taking p copies of 3-GDD (3, 3, 5, 12, 8) together with q − p copies of Example 9.
Corollary 21. There exists a 3-GDD (3, 3, 5, 9q + 3p + 6, 11q − 3p + 4) for p ≤ q.
Proof. Taking blocks of 3-GDD (3, 3, 5, 9q + 3p, 11q − 3p) together with blocks of Example 10 give 3-GDD (3, 3, 5, 9q + 3p + 6, 11q − 3p + 4).
Corollary 22. For all p ≥ 1, 3-(9, 5, 30p) exists.
Proof. Blocks of such design are obtained by taking p-copies of 3-GDD (3, 3, 5, 12, 8) together with 2p-copies of Example 9.
Corollary 23. There exists a 3-(9, 5, 30p + 15) for all p ≥ 0.
Proof. For p ≥ 0, blocks of 3-(9, 5, 30p + 15) are obtained by joining p-copies of blocks of 3-GDD (3, 3, 5, 12, 8), 2p + 1-copies of blocks of Example 9 and blocks of Example 10.
The next Theorem discusses the situation in which the existence of a 3′-GDD (Definition 2) guarantees the existence of 3-PBIBD (Definition 4).
Theorem 24 (Block Complementation). Let k ≤ mn − 3. If a 3′-GDD (n, m, k, Λ1, Λ2) exists, then a 3-PBIBD (n, m, nm − k, θ1, θ2, θ3) also exists, where θ1 = b − 3r + 3λ1 − Λ1, θ2 = b − 3r + λ1 + 2λ2 − Λ2, θ3 = b − 3r + 3λ2 − Λ2. r, and λ1&λ2, respectively, are the replication number, number of first associate pairs, and number of second associate pairs in the 3′-GDD.
Proof. Suppose a 3′-GDD (n, m, k, Λ1, Λ2) exists.
Let (, ) is a 3-GDD (n, m, k, Λ1, Λ2), where is a mn set of points partitioned in to m groups of size n each, and is a collection of k-subsets (blocks) of .
To Show (,{: }) is a 3-PBIBD (n, m, mn − k, θ1, θ2, θ3).
This design has mn points partitioned in to m-parts (groups) of size n, and every block contains mn − k ≥ 3 symbols.
To show every triple of type,
- (i)
(3,0) occurs in θ1 = b − 3r + 3λ1 − Λ1 blocks
- (ii)
(2,1) occurs in θ2 = b − 3r + λ1 + 2λ1 − Λ2 blocks
- (iii)
(1,1,1) occurs in θ3 = b − 3r + 3λ2 − Λ2 blocks
- (1)
To show every triple of type (3,0) occurs in θ1 = b − 3r + 3λ1 − Λ1 blocks,
-
Let (x, y, z) is triple of type (3,0) in (, ). There are 3r − 3λ1 + Λ1 blocks containing x or y or z (containing at least one of them), which means b − 3r + 3λ1 − Λ1 blocks in (, ) do not contain any one of the three elements.
-
Therefore, in (, {: }), and (x, y, z) occurs in θ1 = b − 3r + 3λ1 − Λ1 blocks.
- (2)
To show every triple of type (2,1) occurs in θ2 = b − 3r + λ1 + 2λ2 − Λ2 blocks. Let (x, y, z) is triple of type (2,1) in (, ). There are 3r − λ1 − 2λ2 + Λ2 blocks containing x or y or z (each block containing (x, y, z) contains one first and two second associate pairs).
-
Thus, in (, {: }), there are θ2 = b − 3r + λ1 + 2λ1 − Λ2 blocks containing x, y, and z.
- (3)
Similarly, if (x, y, z) is triple of type (1,1,1) in (, ), there are 3r − 3λ2 + Λ2 blocks containing x or y or z (and each block containing (x, y, z) contains three second associate pairs), and as a result there are θ3 = b − 3r + 3λ2 − Λ2 blocks not containing the triple.
- (1)
Thus, in (, {: }), there are θ3 = b − 3r + 3λ2 − Λ2 blocks containing x, y and z.
Corollary 25.
- (1)
If a 3′-GDD (3, 3, 4, Λ1, Λ2) exists then 3-GDD (3, 3, 5, (9Λ2 + Λ1)/4, (11Λ2 − Λ1)/4) exists
- (2)
If a 3-GDD (3, 3, 5, μ1, μ2) exists, then 3′-GDD (3, 3, 4, (11μ1 − 9μ2)/5, (μ1 + μ2)/5) exists
Proof.
- (a)
Suppose 3′-GDD (3, 3, 4, Λ1, Λ2) exists
-
By Theorem 24, when m = 3 and k = 4, a 3-PBIBD (3, 3, 5, θ1, θ2, θ3) exists, and n = 3 yields θ1 = θ2 = (9Λ2 + Λ1)/4 and θ3 = (11Λ2 − Λ1)/4.
- (b)
If a 3-GDD (3, 3, 5, μ1, and μ2) exists, then taking the complement of its blocks gives a 3-PBIBD (3, 3, 4, β1, β2, β3), where β1 = (11μ1 − 9μ2)/5, β2 = β3 = (μ1 + μ2)/5.
As a result of Corollary 25(b), we have the following examples of a 3′-GDDs when k = 4.
Example 11. A 3′-GDD (3, 3, 4, 6, 2) exists and its blocks are obtained by taking the complement of the blocks of Example 10.
Example 12. A 3-(9, 4, 6) exists. Its blocks are obtained by combining the complements of the blocks of Examples 9 and 10.
In general, taking the complements of the blocks of Corollary 23, the following result follows.
Corollary 26. For all p ≥ 0, a 3–(9, 4, 12p + 6) exists.
6. Conclusions
Both GDDs and t-designs have been studied and have important applications in the field of Combinatorics. These two concepts have been combined to define a 3-GDD. This new definition has the potential to raise many more generalizations and challenging existence problems.
In this paper, we mainly used Definition 5 to study a special type of combinatorial design called a 3-GDD with three groups and block size five, denoted by 3-GDD (n, 3, 5, μ1, μ2). In this work, we have established some necessary conditions for the existence of such designs (Theorems 7 and 11), proved the nonexistence of a 3-GDD (n, 3, 5, μ1, 0) when n ≤ 5 (Theorem 12), and when n ≥ 6, we have shown several existence cases for 3-GDD (n, 3, 5, μ1, 0) (Theorems 17 and 18). In addition, the relationship between 3′-GDD (n, m, k , Λ1, Λ2) (Definition 2) and 3-PBIBD is explained in Theorem 24, and when n = 3, Corollary 25 shows the existence of a 3′-GDD (n, 3, 4, Λ1, Λ2) guarantees the existence of 3-GDD(3, 3, 5, (9Λ2 + Λ1)/4, (11Λ2 − Λ1)/4), while the existence of 3-GDD (3, 3, 5, μ1, μ2) shows the existence of 3′-GDD (3, 3, 4, (11μ1 − 9μ2)/5, (μ1 + μ2)/5). Lastly, we have presented many families of existences for the 3-GDD when n = 3.
6.1. Future Work
- (1)
This research work covers more possibilities for further studies and applications. For example, we can consider a t-GDD instead of only t = 3.
-
We are also thankful to a referee for suggesting future direction for this study as follows.
- (2)
To increase the importance of such designs, overall efficiency for a 3-GDD should be defined.
- (3)
A GDD with parameters: v = mn, b, r, k, μ1 = 0, μ2 = 1 is applicable in the construction of earlier regular low-density parity-check (LDPC) codes free of 4−cycles [16]. Is a 3-GDD under certain conditions also applicable in LDPC codes?
- (4)
Discuss the resolvability of 3-GDDs.
Conflicts of Interest
The authors declare that there are no conflicts of interest regarding the publication of this paper.
Acknowledgments
The authors thank the referees for their valuable suggestions and insightful comments which helped us to improve the paper. The first author also acknowledges the support he received from ISP (International Science Program, Uppsala University, Sweden) and Simons Foundation (Research and Graduate Studies in Mathematics and its Applications).
Open Research
Data Availability
No data were used to support this study.