Namespaces
Variants
Actions

Difference between revisions of "Transversal system"

From Encyclopedia of Mathematics
Jump to: navigation, search
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
How to Cite This Entry:
Transversal system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Transversal_system&oldid=49025
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article