Difference between revisions of "Transversal system"
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
m (fixing spaces) |
||
Line 11: | Line 11: | ||
{{TEX|done}} | {{TEX|done}} | ||
− | ''transversal design, transversal scheme, - | + | ''transversal design, transversal scheme, T -system'' |
− | system'' | ||
A system T _ {0} ( m, t) | A system T _ {0} ( m, t) | ||
Line 20: | Line 19: | ||
Namely: a transversal system T _ {0} ( m, t) | Namely: a transversal system T _ {0} ( m, t) | ||
is a system of t ^ {2} | is a system of t ^ {2} | ||
− | sets Y _ {1} \dots Y _ {t ^ {2} } ( | + | sets Y _ {1} \dots Y _ {t ^ {2} } (blocks or transversals), containing m |
− | blocks or transversals), containing m | ||
elements each and such that: | elements each and such that: | ||
Line 42: | Line 40: | ||
transversals in T _ {0} ( m, t) | transversals in T _ {0} ( m, t) | ||
is called parallel if no two of them intersect. If a transversal design T _ {0} ( m, t) | is called parallel if no two of them intersect. If a transversal design T _ {0} ( m, t) | ||
− | contains e ( | + | contains e (or more) parallel classes, then it is denoted by T _ {e} ( m, t) . |
− | or more) parallel classes, then it is denoted by T _ {e} ( m, t) . | ||
Some of the basic properties of transversal systems are: | Some of the basic properties of transversal systems are: | ||
Line 78: | Line 75: | ||
and Q _ {1} \dots Q _ {m} , | and Q _ {1} \dots Q _ {m} , | ||
let T | let T | ||
− | be a t - | + | be a t -subset of Q _ {1} \cup {} \dots \cup Q _ {m} |
− | subset of Q _ {1} \cup {} \dots \cup Q _ {m} | ||
and put t _ {i} = | T \cap Q _ {i} | | and put t _ {i} = | T \cap Q _ {i} | | ||
for i = 1 \dots m , | for i = 1 \dots m , |
Revision as of 06:32, 22 February 2022
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 |
Transversal system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Transversal_system&oldid=49025