Page 60 - 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. 60
2.5 Resolvable designs
Exercise 16.
Find a solution to the Heffer’s difference problems when:
(1) v=19
(2) v=21.
Exercise 17.
Construct an embedding of an STS(7) into an STS(27).
2.5 Resolvable designs
A parallel class in a design (V, ) is a set of blocks that partition the set V . A partial
parallel class is a set of blocks that contain no point of the design more than once.
Definition 12. A design (V, ) is resolvable if all its blocks can be partitioned into parallel
classes.
Example 17. A (9, 3, 1) − BIBD is resolvable; parallel classes are R1, R2, R3, R4:
V = {0, 1, . . . , 9},
R1 = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}},
R2 = {{0, 3, 6}, {1, 4, 7}, {2, 5, 8}},
R3 = {{0, 4, 8}, {1, 5, 6}, {2, 3, 7}},
R4 = {{0, 5, 7}, {1, 3, 8}, {2, 4, 6}}.
Definition 13. A Kirkman triple system, KTS(v ), of order v is a resolvable STS(v ) together
with a resolution of its blocks.
Distinct resolutions of a given STS(v ) may form nonisomorphic KTS’s.
Example 18. KTS(15), V = {1, 2, . . . , 15},
R1 = {{1, 2, 3}, {4, 8, 12}, {5, 11, 14}, {6, 9, 15}, {7, 10, 13}},
R2 = {{1, 4, 5}, {2, 12, 14}, {3, 9, 10}, {6, 11, 13}, {7, 8, 15}},
R3 = {{1, 6, 7}, {2, 13, 15}, {3, 8, 11}, {4, 10, 14}, {5, 9, 12}},
R4 = {{1, 8, 9}, {2, 4, 6}, {3, 13, 14}, {5, 10, 15}, {7, 11, 12}},
R5 = {{1, 10, 11}, {2, 5, 7}, {3, 12, 15}, {4, 9, 13}, {6, 8, 14}},
R6 = {{1, 12, 13}, {2, 8, 10}, {3, 5, 6}, {4, 11, 15}, {7, 9, 14}},
R7 = {{1, 14, 15}, {2, 9, 11}, {3, 4, 7}, {5, 8, 13}, {6, 10, 12}}.
The existence problem for Kirkman triple systems was completely solved by Ray-
Chaudhuri and Wilson in 1971, more than 120 years after the problem was posed by
Kirkman.
Theorem 17. A Kirkman triple system of order v exists if and only if v ≡ 3 (mod 6).
A proof of sufficiency bases on two important facts:
Lemma 18. For each v ≡ 1 (mod 3), there exists a (v, {4, 7, 10, 19}, 1) − PBD.
Lemma 19. If there exists a (v, K , 1) − PBD, v ≡ 1 (mod 3), and for each ki ∈ K there exists
a KTS(2ki + 1), then there exists a KTS(6n + 3).
Construction of a Kirkman triple system.
Let v = 6n + 3 and let W = V × {1, 2} ∪ {∞} where |V | = 3n + 1.
Let (V, ) be a (3n + 1, {4, 7, 10, 19}, 1) − PBD.
Exercise 16.
Find a solution to the Heffer’s difference problems when:
(1) v=19
(2) v=21.
Exercise 17.
Construct an embedding of an STS(7) into an STS(27).
2.5 Resolvable designs
A parallel class in a design (V, ) is a set of blocks that partition the set V . A partial
parallel class is a set of blocks that contain no point of the design more than once.
Definition 12. A design (V, ) is resolvable if all its blocks can be partitioned into parallel
classes.
Example 17. A (9, 3, 1) − BIBD is resolvable; parallel classes are R1, R2, R3, R4:
V = {0, 1, . . . , 9},
R1 = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}},
R2 = {{0, 3, 6}, {1, 4, 7}, {2, 5, 8}},
R3 = {{0, 4, 8}, {1, 5, 6}, {2, 3, 7}},
R4 = {{0, 5, 7}, {1, 3, 8}, {2, 4, 6}}.
Definition 13. A Kirkman triple system, KTS(v ), of order v is a resolvable STS(v ) together
with a resolution of its blocks.
Distinct resolutions of a given STS(v ) may form nonisomorphic KTS’s.
Example 18. KTS(15), V = {1, 2, . . . , 15},
R1 = {{1, 2, 3}, {4, 8, 12}, {5, 11, 14}, {6, 9, 15}, {7, 10, 13}},
R2 = {{1, 4, 5}, {2, 12, 14}, {3, 9, 10}, {6, 11, 13}, {7, 8, 15}},
R3 = {{1, 6, 7}, {2, 13, 15}, {3, 8, 11}, {4, 10, 14}, {5, 9, 12}},
R4 = {{1, 8, 9}, {2, 4, 6}, {3, 13, 14}, {5, 10, 15}, {7, 11, 12}},
R5 = {{1, 10, 11}, {2, 5, 7}, {3, 12, 15}, {4, 9, 13}, {6, 8, 14}},
R6 = {{1, 12, 13}, {2, 8, 10}, {3, 5, 6}, {4, 11, 15}, {7, 9, 14}},
R7 = {{1, 14, 15}, {2, 9, 11}, {3, 4, 7}, {5, 8, 13}, {6, 10, 12}}.
The existence problem for Kirkman triple systems was completely solved by Ray-
Chaudhuri and Wilson in 1971, more than 120 years after the problem was posed by
Kirkman.
Theorem 17. A Kirkman triple system of order v exists if and only if v ≡ 3 (mod 6).
A proof of sufficiency bases on two important facts:
Lemma 18. For each v ≡ 1 (mod 3), there exists a (v, {4, 7, 10, 19}, 1) − PBD.
Lemma 19. If there exists a (v, K , 1) − PBD, v ≡ 1 (mod 3), and for each ki ∈ K there exists
a KTS(2ki + 1), then there exists a KTS(6n + 3).
Construction of a Kirkman triple system.
Let v = 6n + 3 and let W = V × {1, 2} ∪ {∞} where |V | = 3n + 1.
Let (V, ) be a (3n + 1, {4, 7, 10, 19}, 1) − PBD.
