Page 61 - 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. 61
iusz Meszka: Combinatorial Designs 49
For each block B ∈ , put on the set B × {1, 2} ∪ {∞} a copy of a KTS(2|B | + 1) with a
resolution B in such a way that {x1, x2, ∞} is a triple for each x ∈ B .
Let RBx be a parallel class of B containing the triple {x1, x2, ∞}. Then Rx = B∈ RBx
is a parallel class on W and = {Rx : x ∈ V } is a resolution of a KTS(v ).
The necessary conditions are also sufficient for the existence of a resolvable (v,k,1)-
BIBD when k is small, namely:
if k = 2, v ≡ 0 (mod 2),
if k = 3, v ≡ 3 (mod 6),
if k = 4, v ≡ 4 (mod 12).
For k = 5, a resolvable (v, 5, 1) − BIBD exists if v ≡ 5 (mod 20) and v = 45, 345, 465, 645, in
which cases the existence problem remains open.
Theorem 20. A resolvable transversal design TD(k , m ) exists if and only if there exists a set
of k − 1 MOLS(m ).
Corollary 21. A resolvable transversal design TD(k , m ) exists if and only if there exists
transversal design TD(k + 1, m ).
When v ≡ 1 (mod 6), the maximum number of pairwise disjoint triples is v −1 . Then
3
the maximum partial parallel class has to miss one point.
Definition 14. A Hanani triple system, HTS(v ), of order v is an STS(v ) with a partition
of its blocks into (v − 1)/2 almost parallel classes and a single partial parallel class with
(v − 1)/6 triples.
Theorem 22. A Hanani triple system of order v exists if and only if v ≡ 1 (mod 6) and
v ∈ {7, 13}.
Exercise 18.
Construct a resolvable (16, 4, 1) − BIBD.
Exercise 19.
Construct a resolvable TD(5, 7).
Exercise 20.
Show that an HTS(7) does not exist.
2.6 Other classes of designs
2.6.1 Affine and projective planes
A finite incidence structure (or finite geometry), P = ( , , I ) is made of a finite set of
points , a finite set of lines , and an incidence relation I between them.
Definition 15. A finite affine plane is a finite incidence structure such that the following
axioms are satisfied:
(A1) any two distinct points are incident with exactly one line,
(A2) for any point P outside a line l there is exactly one line through P that has no point
in common with l ,
For each block B ∈ , put on the set B × {1, 2} ∪ {∞} a copy of a KTS(2|B | + 1) with a
resolution B in such a way that {x1, x2, ∞} is a triple for each x ∈ B .
Let RBx be a parallel class of B containing the triple {x1, x2, ∞}. Then Rx = B∈ RBx
is a parallel class on W and = {Rx : x ∈ V } is a resolution of a KTS(v ).
The necessary conditions are also sufficient for the existence of a resolvable (v,k,1)-
BIBD when k is small, namely:
if k = 2, v ≡ 0 (mod 2),
if k = 3, v ≡ 3 (mod 6),
if k = 4, v ≡ 4 (mod 12).
For k = 5, a resolvable (v, 5, 1) − BIBD exists if v ≡ 5 (mod 20) and v = 45, 345, 465, 645, in
which cases the existence problem remains open.
Theorem 20. A resolvable transversal design TD(k , m ) exists if and only if there exists a set
of k − 1 MOLS(m ).
Corollary 21. A resolvable transversal design TD(k , m ) exists if and only if there exists
transversal design TD(k + 1, m ).
When v ≡ 1 (mod 6), the maximum number of pairwise disjoint triples is v −1 . Then
3
the maximum partial parallel class has to miss one point.
Definition 14. A Hanani triple system, HTS(v ), of order v is an STS(v ) with a partition
of its blocks into (v − 1)/2 almost parallel classes and a single partial parallel class with
(v − 1)/6 triples.
Theorem 22. A Hanani triple system of order v exists if and only if v ≡ 1 (mod 6) and
v ∈ {7, 13}.
Exercise 18.
Construct a resolvable (16, 4, 1) − BIBD.
Exercise 19.
Construct a resolvable TD(5, 7).
Exercise 20.
Show that an HTS(7) does not exist.
2.6 Other classes of designs
2.6.1 Affine and projective planes
A finite incidence structure (or finite geometry), P = ( , , I ) is made of a finite set of
points , a finite set of lines , and an incidence relation I between them.
Definition 15. A finite affine plane is a finite incidence structure such that the following
axioms are satisfied:
(A1) any two distinct points are incident with exactly one line,
(A2) for any point P outside a line l there is exactly one line through P that has no point
in common with l ,
