Content deleted Content added
Erel Segal (talk | contribs) added Category:Set families using HotCat |
Erel Segal (talk | contribs) |
||
Line 32:
== Generalizations ==
A '''partial transversal''' is a set containing at most one element from each member of the collection, or (in the stricter form of the concept) a set with an injection from the set to ''C''.
An '''independent transversal''' (also called a [[Rainbow independent set|'''rainbow independent set''']] or '''independent system of representatives''') is a transversal which is also an [[Independent set (graph theory)|independent set]] of a given graph. To explain the difference in figurative terms, consider a faculty with ''m'' departments, where the faculty dean wants to construct a committee of ''m'' members, one member per department. Such a committee is a transversal. But now, suppose that some faculty members dislike each other and do not agree to sit in the committee together. In this case, the committee must be an independent transversal, where the underlying graph describes the "dislike" relations.
The transversals of a finite collection ''C'' of finite sets form the basis sets of a [[matroid]], the "transversal matroid" of ''C''. The independent sets of the transversal matroid are the partial transversals of ''C''.<ref>{{citation|page=48|title=Matroid Theory|volume=3|series=Oxford graduate texts in mathematics|first=James G.|last=Oxley | authorlink = James Oxley|publisher=Oxford University Press|year=2006|isbn=978-0-19-920250-8}}.</ref>
| |||