Transversal (combinatorics): Difference between revisions
m cat |
more general meanings |
||
| Line 1: | Line 1: | ||
Given a collection ''C'' of disjoint [[set theory|sets]], a '''transversal''' is a set containing exactly one member of each of them. In case that the original sets are not disjoint, there are several variations. One variation is that there is a [[bijection]] ''f'' from the transversal to ''C'' such that ''x'' is an element of ''f''(''x'') for each ''x'' in the transversal. Another is merely that the transversal have non-empty intersection with each set in ''C''. |
|||
| ⚫ | |||
As an example of the first (disjoint-sets) meaning of ''transversal'', |
|||
| ⚫ | |||
A transversal in a [[Latin square]] of order ''n'' is a collection of ''n'' matrix positions comprising one from each row and one from each column, such that the symbols in those positions are distinct. Not all Latin squares have transversals. |
|||
[[Category:Group theory]] |
[[Category:Group theory]] |
||
[[Category:Set theory]] |
|||
Revision as of 06:21, 27 November 2004
Given a collection C of disjoint sets, a transversal is a set containing exactly one member of each of them. In case that the original sets are not disjoint, there are several variations. One variation is that there is a bijection f from the transversal to C such that x is an element of f(x) for each x in the transversal. Another is merely that the transversal have non-empty intersection with each set in C.
As an example of the first (disjoint-sets) meaning of transversal, in group theory, given a subgroup H of a group G, a right (respectively left) transversal is a set containing exactly one element from each right (respectively left) coset of H.
A transversal in a Latin square of order n is a collection of n matrix positions comprising one from each row and one from each column, such that the symbols in those positions are distinct. Not all Latin squares have transversals.