Page 64 - 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. 64
2.6 Other classes of designs
2.6.3 G -designs
Definition 18. A G -design of order v and index λ (or (λKn ,G )-design) is a G -decomposi-
tion of a complete λ-multigraph λKn . A (λKn ,G )-design is balanced if each vertex of λKn
occurs in the same number of copies of G .
Theorem 29. There exists a (λKn , K1,k )-design if and only if n ≥ k + 1 and λn (n − 1) ≡ 0
(mod 2k ).
Theorem 30. There exists a (λKn , Pk )-design if and only if n ≥ k and λn (n − 1) ≡ 0
(mod (2k − 2)).
Example 21. A (K6, P4)-design:
V = {0, 1, 2, 3, 4, 5},
= {(0, 1, 2, 4), (0, 2, 3, 5), (0, 3, 4, 1), (0, 4, 5, 2), (0, 5, 1, 3)}.
Conjecture. There exists a (K2n+1, T )-design for each tree T with n edges.
Exercise 24.
Construct a (2K7, K1,6)-design.
2.6.4 t -designs
Definition 19. A t − (v, k , λ)-design is a pair (V, ) where |V | = v and is a collection
of k -element subsets of V (blocks) with the property that each t -element subset of V is
contained in exactly λ blocks.
An ordered quadruple of positive integers (λ, t , k , v ) is called admissible if λs =
λ( v −s )/( k −s ) is an integer for each 0 ≤ s < t .
t −s t −s
A Steiner quadruple system of order v (SQS(v )) is a 3 − (v, 4, 1)-design.
Example 22. A cyclic SQS(10):
V = Z10. The base blocks are: B1 = {0, 1, 3, 4}, B2 = {0, 1, 2, 6}, B3 = {0, 2, 4, 7}.
Theorem 31. An SQS(v ) exists if and only if v ≡ 2, 4 (mod 6).
Exercise 25.
Construct an SQS(8).
2.6.5 Room squares
Definition 20. Let S be a set of n + 1 elements (symbols). A Room square of side n is an
n × n array, R, that satisfies the following properties:
(1) every cell of R is either empty or contains an unordered pair of symbols from S,
(2) every symbol of S occurs exactly once in each row and exactly once in each column
of R,
(3) every unordered pair of symbols occurs in precisely one cell in R.
2.6.3 G -designs
Definition 18. A G -design of order v and index λ (or (λKn ,G )-design) is a G -decomposi-
tion of a complete λ-multigraph λKn . A (λKn ,G )-design is balanced if each vertex of λKn
occurs in the same number of copies of G .
Theorem 29. There exists a (λKn , K1,k )-design if and only if n ≥ k + 1 and λn (n − 1) ≡ 0
(mod 2k ).
Theorem 30. There exists a (λKn , Pk )-design if and only if n ≥ k and λn (n − 1) ≡ 0
(mod (2k − 2)).
Example 21. A (K6, P4)-design:
V = {0, 1, 2, 3, 4, 5},
= {(0, 1, 2, 4), (0, 2, 3, 5), (0, 3, 4, 1), (0, 4, 5, 2), (0, 5, 1, 3)}.
Conjecture. There exists a (K2n+1, T )-design for each tree T with n edges.
Exercise 24.
Construct a (2K7, K1,6)-design.
2.6.4 t -designs
Definition 19. A t − (v, k , λ)-design is a pair (V, ) where |V | = v and is a collection
of k -element subsets of V (blocks) with the property that each t -element subset of V is
contained in exactly λ blocks.
An ordered quadruple of positive integers (λ, t , k , v ) is called admissible if λs =
λ( v −s )/( k −s ) is an integer for each 0 ≤ s < t .
t −s t −s
A Steiner quadruple system of order v (SQS(v )) is a 3 − (v, 4, 1)-design.
Example 22. A cyclic SQS(10):
V = Z10. The base blocks are: B1 = {0, 1, 3, 4}, B2 = {0, 1, 2, 6}, B3 = {0, 2, 4, 7}.
Theorem 31. An SQS(v ) exists if and only if v ≡ 2, 4 (mod 6).
Exercise 25.
Construct an SQS(8).
2.6.5 Room squares
Definition 20. Let S be a set of n + 1 elements (symbols). A Room square of side n is an
n × n array, R, that satisfies the following properties:
(1) every cell of R is either empty or contains an unordered pair of symbols from S,
(2) every symbol of S occurs exactly once in each row and exactly once in each column
of R,
(3) every unordered pair of symbols occurs in precisely one cell in R.
