Transversal system

transversal design, transversal scheme, $ T $-system

A system $ T _ {0} ( m, t) $ of sets defined for a given collection of $ m $ pairwise-disjoint finite sets $ S _ {1}, \dots, S _ {m} $, each of which has cardinality $ t $. Namely: a transversal system $ T _ {0} ( m, t) $ is a system of $ t ^ {2} $ sets $ Y _ {1}, \dots, Y _ {t ^ {2} } $ (blocks or transversals), containing $ m $ elements each and such that:

1) $ | Y _ {j} \cap S _ {i} | = 1 $; $ i = 1, \dots, m $; $ j = 1, \dots, t ^ {2} $;

2) $ | Y _ {j} \cap Y _ {k} | \leq 1 $ for $ j \neq k $.

In a transversal design, any two elements $ a \in S _ {i} $ and $ b \in S _ {j} $, $ i \neq j $, occur together in exactly one block. The existence of a transversal design $ T _ {0} ( m, t) $ is equivalent to the existence of an orthogonal array $ \mathop{\rm OA} ( t, m) $.

Transversal designs are used in recursive constructions of block designs (cf. Block design).

A set of $ t $ transversals in $ T _ {0} ( m, t) $ is called parallel if no two of them intersect. If a transversal design $ T _ {0} ( m, t) $ contains $ e $ (or more) parallel classes, then it is denoted by $ T _ {e} ( m, t) $.

Some of the basic properties of transversal systems are:

a) if $ T _ {d} ( m, s) $ and $ T _ {e} ( m, t) $ exist, then so does $ T _ {de} ( m, st) $;

b) $ T _ {t} ( m - 1, t) $ exists if and only if $ T _ {0} ( m, t) $ exists.

References

[1]	M. Hall, "Combinatorial theory" , Wiley (1986)
[2]	H. Hanani, "The existence and construction of balanced incomplete block designs" Ann. Math. Stat. , 32 (1961) pp. 361–386

Comments

The finite sets $ S _ {1}, \dots, S _ {m} $ making up the design are called point classes or point groups.

The existence of a transversal design $ T _ {0} ( m, t) $ is equivalent to the existence of $ m - 2 $ mutually orthogonal Latin squares of order $ t $. If a $ T _ {0} ( m, t) $ exists, and $ t > 1 $, then $ m \leq t + 1 $.

See also [a1]–[a3] for the recursive construction of and existence results for transversal designs (and of their generalization "transversal design with holes" , [a2]).

One of the most important results on recursive construction of transversal designs (due to R.M. Wilson [a4], see also [a1]) is as follows:

Let $ D $ be a $ T _ {0} ( k+ m, s) $ with point classes $ P _ {1}, \dots, P _ {k} $ and $ Q _ {1}, \dots, Q _ {m} $, let $ T $ be a $ t $-subset of $ Q _ {1} \cup {} \dots \cup Q _ {m} $ and put $ t _ {i} = | T \cap Q _ {i} | $ for $ i = 1, \dots, m $, and $ u _ {B} = | B \cap T | $ for every block $ B $ of $ D $. Assume the existence of $ T _ {0} ( k , t _ {i} ) $ for $ i = 1, \dots, m $ and of $ T _ {u _ {B} } ( k , n + u _ {B} ) $ for each block $ B $ of $ D $. Then $ T _ {0} ( k, ns+ t ) $ also exists.

Transversals designs (and their dual structures, nets) are also of considerable geometric and algebraic interest. For instance, a $ T _ {0} ( s+ 1, s) $ is equivalent to an affine or projective plane of order $ s $, and a $ T _ {0} ( 3, s) $ is basically the same as a quasi-group of order $ s $. Thus, the geometric and algebraic properties of transversal designs (including the study of their automorphism groups) have found considerable interest, cf. [a4].

References

[a1]	T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1986)
[a2]	A.E. Brouwer, "Recursive constructions of mutually orthogonal Latin squares" Ann. Discr. Math. , 46 (1991) pp. 149–168
[a3]	D. Jungnickel, "Latin squares, their geometries and their groups: a survey" D. Ray-Chaudhuri (ed.) , Coding Theory and Design Theory , IMA Vol. Math. Appl. , 21 , Springer (1990) pp. 166–225
[a4]	R.M. Wilson, "Concerning the number of mutually orthogonal Latin squares" Discr. Math. , 9 (1974) pp. 181–198
[a5]	H. Hanani, "Balanced incomplete block designs and related designs" Discrete Math. , 11 (1975) pp. 255–369