transversal

The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. (September 2008)

In combinatorial mathematics, given a collection C of sets, a transversal is a set containing exactly one element from each member of the collection: it is a section of the quotient map induced by the collection. If the original sets are not disjoint, there are several different definitions. 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. Then the set is also called a system of distinct representatives. A less restrictive definition requires that the transversal just has a non-empty intersection with each member of C.

A partial transversal is a set containing at most one element from each member of the collection, or a set with an injection from the set to C.

Examples

As an example of the 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.

Given a direct product of groups , then H is a transversal for the cosets of K, and conversely.

• The marriage theorem gives necessary and sufficient conditions for possibly overlapping subsets to have a transversal.

References

• Mirsky, Leon (1971). Transversal Theory: An account of some aspects of combinatorial mathematics. Academic Press. ISBN 0-12-498550-5.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it. v • d • e