Page 57 - 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. 57
iusz Meszka: Combinatorial Designs 45
(3) 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
(4) place {∞1, ∞2, ∞3, ∞4} in .
Then (V , , ) is a TD(4, 3m + 1).
Exercise 10.
(1) Construct a PBD(10, {3, 4}, 1).
(2) Construct a PBD(12, {3, 4}, 1).
(3) Construct a PBD(11, {3, 5}, 1).
Exercise 11.
Show that a PBD(8, {3, 4}, 1) does not exist.
Exercise 12.
(1) Construct a 3 − GDD of type 35.
(2) Construct a 4 − GDD of type 34.
Exercise 13.
Construct a TD(4, 13).
2.4 Steiner triple systems
The first class of intensively studied designs were BIBD’s with block size 3 and λ = 1.
Definition 11. A Steiner triple system, STS(v ), of order v is a (v, 3, 1) − BIBD. Blocks of an
STS(v ) are often called triples.
The arithmetic necessary conditions for the existence of an STS(v ) reduce to v ≡ 1, 3
(mod 6). This is also a sufficient condition, what was proven in 1847 by Kirkman. One of
the simplest known direct constructions is due to Bose and Skolem.
Bose construction (for STS(v ) when v ≡ 3 (mod 6)).
Let v = 6k + 3 and let (Q, ◦) be an idempotent commutative quasigroup of order 2k + 1,
where Q = {0, 1, . . . , 2k }. Let V = Q × {1, 2, 3}, and define to contain the following two
types of triples:
(1) for 0 ≤ i ≤ 2k , {(i , 1), (i , 2), (i , 3)} ∈ ,
(2) for 0 ≤ i < j ≤ 2k , {(i , 1), (j , 1), (i ◦ j , 2)} ∈ , {(i , 2), (j , 2), (i ◦ j , 3)} ∈ ,
{(i , 3), (j , 3), (i ◦ j , 1)} ∈ .
Skolem construction (for STS(v ) when v ≡ 1 (mod 6)).
Let v = 6k + 1 and let (Q, ◦) be a half-idempotent commutative quasigroup of order 2k ,
where Q = {0, 1, . . . , 2k − 1}. Let V = (Q × {1, 2, 3}) ∪ {∞}, and define as follows:
(1) for 0 ≤ i ≤ k − 1, {(i , 1), (i , 2), (i , 3)} ∈ ,
(2) for 0 ≤ i ≤ k − 1, {∞, (k + i , 1), (i , 2)} ∈ , {∞, (k + i , 2), (i , 3)} ∈ ,
{∞, (k + i , 3), (i , 1)} ∈ ,
(3) for 0 ≤ i < j ≤ 2k − 1, {(i , 1), (j , 1), (i ◦ j , 2)} ∈ , {(i , 2), (j , 2), (i ◦ j , 3)} ∈ ,
{(i , 3), (j , 3), (i ◦ j , 1)} ∈ .
An STS(v ) is cyclic if it admits an automorphism which is a single cycle of length v .
Then all triples may be represented by base triples, one for each orbit of triples under
a cyclic automorphism. The existence of cyclic Steiner triple systems may be proven by
(3) 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
(4) place {∞1, ∞2, ∞3, ∞4} in .
Then (V , , ) is a TD(4, 3m + 1).
Exercise 10.
(1) Construct a PBD(10, {3, 4}, 1).
(2) Construct a PBD(12, {3, 4}, 1).
(3) Construct a PBD(11, {3, 5}, 1).
Exercise 11.
Show that a PBD(8, {3, 4}, 1) does not exist.
Exercise 12.
(1) Construct a 3 − GDD of type 35.
(2) Construct a 4 − GDD of type 34.
Exercise 13.
Construct a TD(4, 13).
2.4 Steiner triple systems
The first class of intensively studied designs were BIBD’s with block size 3 and λ = 1.
Definition 11. A Steiner triple system, STS(v ), of order v is a (v, 3, 1) − BIBD. Blocks of an
STS(v ) are often called triples.
The arithmetic necessary conditions for the existence of an STS(v ) reduce to v ≡ 1, 3
(mod 6). This is also a sufficient condition, what was proven in 1847 by Kirkman. One of
the simplest known direct constructions is due to Bose and Skolem.
Bose construction (for STS(v ) when v ≡ 3 (mod 6)).
Let v = 6k + 3 and let (Q, ◦) be an idempotent commutative quasigroup of order 2k + 1,
where Q = {0, 1, . . . , 2k }. Let V = Q × {1, 2, 3}, and define to contain the following two
types of triples:
(1) for 0 ≤ i ≤ 2k , {(i , 1), (i , 2), (i , 3)} ∈ ,
(2) for 0 ≤ i < j ≤ 2k , {(i , 1), (j , 1), (i ◦ j , 2)} ∈ , {(i , 2), (j , 2), (i ◦ j , 3)} ∈ ,
{(i , 3), (j , 3), (i ◦ j , 1)} ∈ .
Skolem construction (for STS(v ) when v ≡ 1 (mod 6)).
Let v = 6k + 1 and let (Q, ◦) be a half-idempotent commutative quasigroup of order 2k ,
where Q = {0, 1, . . . , 2k − 1}. Let V = (Q × {1, 2, 3}) ∪ {∞}, and define as follows:
(1) for 0 ≤ i ≤ k − 1, {(i , 1), (i , 2), (i , 3)} ∈ ,
(2) for 0 ≤ i ≤ k − 1, {∞, (k + i , 1), (i , 2)} ∈ , {∞, (k + i , 2), (i , 3)} ∈ ,
{∞, (k + i , 3), (i , 1)} ∈ ,
(3) for 0 ≤ i < j ≤ 2k − 1, {(i , 1), (j , 1), (i ◦ j , 2)} ∈ , {(i , 2), (j , 2), (i ◦ j , 3)} ∈ ,
{(i , 3), (j , 3), (i ◦ j , 1)} ∈ .
An STS(v ) is cyclic if it admits an automorphism which is a single cycle of length v .
Then all triples may be represented by base triples, one for each orbit of triples under
a cyclic automorphism. The existence of cyclic Steiner triple systems may be proven by
