Page 56 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 56
2.3 Pairwise balanced designs and group divisible designs
Example 13. A GDD(10, {3, 4}, {1, 3}, 1) of type 1133:
V = {1, 2, . . . , 10},
= {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10}},
= {{1, 4, 7, 10}, {2, 5, 8, 10}, {3, 6, 9, 10}, {1, 5, 9}, {2, 6, 7}, {3, 4, 8}, {1, 6, 8}, {2, 4, 9},
{3, 5, 7}}.
A GDD is uniform if K = {k } and all its groups have the same size m , that is, if it is
of type m u for some positive integer u . The necessary conditions for the existence of a
uniform GDD(v, k , m , λ) of type m u are:
(1) u ≥ k ,
(2) λ(u − 1)m ≡ 0 (mod k − 1),
(3) λu (u − 1)m 2 ≡ 0 (mod k (k − 1)).
Definition 10. A transversal design, TD(k , m ), is a uniform k − GDD of type m k .
In other words, a GDD is a transversal design if and only if each block meets every
group in exactly one point.
Theorem 11. A transversal design TD(k , m ) exists if and only if there exists a set of k − 2
MOLS(m ).
A GDD(v, K ,G , 1) may be viewed as a PBD(v, K ∪G , 1) by considering all groups of the
GDD to be blocks of the PBD, together with blocks of the GDD.
Lemma 12. If there exists a group divisible design (V, , ) with λ = 1, then there exists a
pairwise balanced design (V, ), where = ∪ {G ∈ : |G | ≥ 2}.
Moreover, a GDD(v, K ,G , 1) can be used to built a PBD(v + 1, K ∪ {g + 1 : g ∈ G }, 1)
by adjoining a new point to each group to form new blocks. Conversely, a GDD may be
obtained from a PBD by deleting a point.
Lemma 13. Suppose there exists a group divisible design (V, , ), λ = 1 and ∞ ∈ V .
Define W = V ∪ {∞} and = ∪ {G ∪ {∞} : G ∈ }. Then (W, ) is a pairwise balanced
design.
Certain transversal designs may be obtained using some recursive constructions.
TD(4, m ) → TD(4, 3m ) construction.
Let (V, , ) be a TD(4, m ) and let W = {1, 2, 3}. Let V = V × W and define a collection
of groups and a collection of blocks as follows:
(1) = {G × W : G ∈ }
(2) for each B ∈ , let (B × W, {{a } × W : a ∈ B }, W (B )} be a TD(4, 3) and place the 9
blocks belonging to W (B ) in .
Then (V , , ) is a TD(4, 3m ).
TD(4, m ) with a parallel class → TD(4, 3m + 1) construction.
Let (V, , ) be a TD(4, m ) and let Π be a parallel class of blocks. Let W = {1, 2, 3} and
set V1 = {∞1, ∞2, ∞3, ∞4}. Let V = V × W ∪ V1. Define a collection of groups and a
collection of blocks as follows:
(1) = {(Gi × W ) ∪ {∞i } : Gi ∈ }
(2) for each block B ∈ Π, let ((B × W ) ∪ V1, {({a } × W ) ∪ {∞i } : a ∈ B ∩Gi , i ∈ W }, W (B )} be
a TD(4, 4) with a requirement that {∞1, ∞2, ∞3, ∞4} is a block; place 15 blocks of W (B ) \
{∞1, ∞2, ∞3, ∞4} in
Example 13. A GDD(10, {3, 4}, {1, 3}, 1) of type 1133:
V = {1, 2, . . . , 10},
= {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10}},
= {{1, 4, 7, 10}, {2, 5, 8, 10}, {3, 6, 9, 10}, {1, 5, 9}, {2, 6, 7}, {3, 4, 8}, {1, 6, 8}, {2, 4, 9},
{3, 5, 7}}.
A GDD is uniform if K = {k } and all its groups have the same size m , that is, if it is
of type m u for some positive integer u . The necessary conditions for the existence of a
uniform GDD(v, k , m , λ) of type m u are:
(1) u ≥ k ,
(2) λ(u − 1)m ≡ 0 (mod k − 1),
(3) λu (u − 1)m 2 ≡ 0 (mod k (k − 1)).
Definition 10. A transversal design, TD(k , m ), is a uniform k − GDD of type m k .
In other words, a GDD is a transversal design if and only if each block meets every
group in exactly one point.
Theorem 11. A transversal design TD(k , m ) exists if and only if there exists a set of k − 2
MOLS(m ).
A GDD(v, K ,G , 1) may be viewed as a PBD(v, K ∪G , 1) by considering all groups of the
GDD to be blocks of the PBD, together with blocks of the GDD.
Lemma 12. If there exists a group divisible design (V, , ) with λ = 1, then there exists a
pairwise balanced design (V, ), where = ∪ {G ∈ : |G | ≥ 2}.
Moreover, a GDD(v, K ,G , 1) can be used to built a PBD(v + 1, K ∪ {g + 1 : g ∈ G }, 1)
by adjoining a new point to each group to form new blocks. Conversely, a GDD may be
obtained from a PBD by deleting a point.
Lemma 13. Suppose there exists a group divisible design (V, , ), λ = 1 and ∞ ∈ V .
Define W = V ∪ {∞} and = ∪ {G ∪ {∞} : G ∈ }. Then (W, ) is a pairwise balanced
design.
Certain transversal designs may be obtained using some recursive constructions.
TD(4, m ) → TD(4, 3m ) construction.
Let (V, , ) be a TD(4, m ) and let W = {1, 2, 3}. Let V = V × W and define a collection
of groups and a collection of blocks as follows:
(1) = {G × W : G ∈ }
(2) for each B ∈ , let (B × W, {{a } × W : a ∈ B }, W (B )} be a TD(4, 3) and place the 9
blocks belonging to W (B ) in .
Then (V , , ) is a TD(4, 3m ).
TD(4, m ) with a parallel class → TD(4, 3m + 1) construction.
Let (V, , ) be a TD(4, m ) and let Π be a parallel class of blocks. Let W = {1, 2, 3} and
set V1 = {∞1, ∞2, ∞3, ∞4}. Let V = V × W ∪ V1. Define a collection of groups and a
collection of blocks as follows:
(1) = {(Gi × W ) ∪ {∞i } : Gi ∈ }
(2) for each block B ∈ Π, let ((B × W ) ∪ V1, {({a } × W ) ∪ {∞i } : a ∈ B ∩Gi , i ∈ W }, W (B )} be
a TD(4, 4) with a requirement that {∞1, ∞2, ∞3, ∞4} is a block; place 15 blocks of W (B ) \
{∞1, ∞2, ∞3, ∞4} in
