Transversal (combinatorics): Difference between revisions
Salix alba (talk | contribs) fix link to set (mathematics) using AWB |
Chris-martin (talk | contribs) {{context}} |
||
| Line 1: | Line 1: | ||
{{otheruses}} |
{{otheruses}} |
||
{{context|date=September 2008}} |
|||
In [[combinatorics|combinatorial]] mathematics, given a collection ''C'' of [[set theory|sets]], a '''transversal''' is a set containing exactly one element from each member of the collection: it is a [[Section (category theory)|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. A less restrictive definition requires that the transversal just has a non-empty intersection with each member of ''C''. |
In [[combinatorics|combinatorial]] mathematics, given a collection ''C'' of [[set theory|sets]], a '''transversal''' is a set containing exactly one element from each member of the collection: it is a [[Section (category theory)|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. A less restrictive definition requires that the transversal just has a non-empty intersection with each member of ''C''. |
||
Revision as of 18:43, 29 September 2008
 | This article provides insufficient context for those unfamiliar with the subject. (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. A less restrictive definition requires that the transversal just has a non-empty intersection with each member of 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.
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |