Page 55 - 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. 55
iusz Meszka: Combinatorial Designs 43
(3,3)-Sudoku critical sets are known for all sizes from 17 to 35. For instance, the exis-
tence of a (3,3)-Sudoku critical set is still unsettled for the size 16. The number of distinct
(n, n)-Sudoku latin squares for n = 1, 2 and 3 is 1, 288 and 6, 670, 903, 752, 021, 072, 936, 960,
respectively. The number of inequivalent (n, n )-Sudoku latin squares for n = 1, 2 and 3
is 1, 2 and 5, 472, 730, 538, respectively.
Exercise 7.
(1) Find an idempotent commutative latin square of order 5.
(2) Find a half-idempotent commutative latin square of order 6.
Exercise 8.
Construct a set of two MOLS(3).
Exercise 9.
Complete a Sudoku critical set from the Example 11.
2.3 Pairwise balanced designs and group divisible designs
Relaxing some of conditions in the definition of BIBD leads to other classes of designs.
One of them concerns the case when all blocks do not have to have the same size.
Definition 8. Let λ be a positive integer and K be a set of positive integers. A pairwise
balanced design, PBD(v, K , λ), of order v with block sizes from K is a pair (V, ) where V
is a set of cardinality v and is a collection of subsets of V called blocks such that each
block B ∈ has size |B | ∈ K and every pair of distinct elements of V occurs in exactly λ
blocks.
Example 12. A PBD(6, {3, 4}, 3):
V = {1, 2, 3, 4, 5, 6},
= {{1, 2, 3, 4}, {1, 3, 4, 5}, {1, 4, 5, 6}, {2, 3, 4, 6}, {2, 4, 5, 6}, {1, 2, 5}, {1, 2, 6}, {1, 3, 6},
{2, 3, 5}, {3, 5, 6}}.
If a PBD(v, K , λ) has bi blocks of size ki for each ki ∈ K , then λ v = i bi ki .
2 2
For a set of positive integers K , let α(K ) = gcd{k −1 : k ∈ K } and β (K ) = gcd{k (k −1) :
k ∈ K }. Then the necessary conditions for the existence of a PBD(v, K , λ) are:
(1) λ(v − 1) ≡ 0 (mod α(K )), and
(2) λv (v − 1) ≡ 0 (mod β (K )).
Remark. Let K = {v }. If there exists a PBD(v, K , 1), then v ≥ l (s − 1) + 1, where l and s are
the largest and the smallest sizes, respectively, of blocks in a PBD.
Definition 9. Let K and G be sets of positive integers and λ be a positive integer. A group
divisible design of order v and index λ, GDD(v, K ,G , λ), is a triple (V, , ) where V is a
finite set of cardinality v , is a partition of V into groups whose sizes belong to G , and
is a collection of subsets of V called blocks such that each B ∈ has |B | ∈ K and every
pair of distinct elements of V is contained in exactly λ blocks or in one group, but not
both. Moreover, | | ≥ 2.
Given a GDD(v, K ,G , λ) with a i groups of size gi, i = 1, 2, . . . , s (so that s a i g i =
we use exponential notation for the group type. If K = {k i =1 1,
a a a
v ), g 1 1 g 2 2 . . . g s s } and λ =
then we write k − GDD.
(3,3)-Sudoku critical sets are known for all sizes from 17 to 35. For instance, the exis-
tence of a (3,3)-Sudoku critical set is still unsettled for the size 16. The number of distinct
(n, n)-Sudoku latin squares for n = 1, 2 and 3 is 1, 288 and 6, 670, 903, 752, 021, 072, 936, 960,
respectively. The number of inequivalent (n, n )-Sudoku latin squares for n = 1, 2 and 3
is 1, 2 and 5, 472, 730, 538, respectively.
Exercise 7.
(1) Find an idempotent commutative latin square of order 5.
(2) Find a half-idempotent commutative latin square of order 6.
Exercise 8.
Construct a set of two MOLS(3).
Exercise 9.
Complete a Sudoku critical set from the Example 11.
2.3 Pairwise balanced designs and group divisible designs
Relaxing some of conditions in the definition of BIBD leads to other classes of designs.
One of them concerns the case when all blocks do not have to have the same size.
Definition 8. Let λ be a positive integer and K be a set of positive integers. A pairwise
balanced design, PBD(v, K , λ), of order v with block sizes from K is a pair (V, ) where V
is a set of cardinality v and is a collection of subsets of V called blocks such that each
block B ∈ has size |B | ∈ K and every pair of distinct elements of V occurs in exactly λ
blocks.
Example 12. A PBD(6, {3, 4}, 3):
V = {1, 2, 3, 4, 5, 6},
= {{1, 2, 3, 4}, {1, 3, 4, 5}, {1, 4, 5, 6}, {2, 3, 4, 6}, {2, 4, 5, 6}, {1, 2, 5}, {1, 2, 6}, {1, 3, 6},
{2, 3, 5}, {3, 5, 6}}.
If a PBD(v, K , λ) has bi blocks of size ki for each ki ∈ K , then λ v = i bi ki .
2 2
For a set of positive integers K , let α(K ) = gcd{k −1 : k ∈ K } and β (K ) = gcd{k (k −1) :
k ∈ K }. Then the necessary conditions for the existence of a PBD(v, K , λ) are:
(1) λ(v − 1) ≡ 0 (mod α(K )), and
(2) λv (v − 1) ≡ 0 (mod β (K )).
Remark. Let K = {v }. If there exists a PBD(v, K , 1), then v ≥ l (s − 1) + 1, where l and s are
the largest and the smallest sizes, respectively, of blocks in a PBD.
Definition 9. Let K and G be sets of positive integers and λ be a positive integer. A group
divisible design of order v and index λ, GDD(v, K ,G , λ), is a triple (V, , ) where V is a
finite set of cardinality v , is a partition of V into groups whose sizes belong to G , and
is a collection of subsets of V called blocks such that each B ∈ has |B | ∈ K and every
pair of distinct elements of V is contained in exactly λ blocks or in one group, but not
both. Moreover, | | ≥ 2.
Given a GDD(v, K ,G , λ) with a i groups of size gi, i = 1, 2, . . . , s (so that s a i g i =
we use exponential notation for the group type. If K = {k i =1 1,
a a a
v ), g 1 1 g 2 2 . . . g s s } and λ =
then we write k − GDD.
