Transversal (combinatorics): Difference between revisions

Revision as of 20:35, 10 August 2020

Revision as of 07:40, 25 October 2020

Line 43:

An '''independent transversal''' (also called a '''[[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.

Another generalization of the concept of a transversal would be a set that just has a non-empty intersection with each member of ''C''. An example of the latter would be a [[Bernstein set|'''[[Bernstein set]]''']], which is defined as a set that has a non-empty intersection with each set of ''C'', but contains no set of ''C'', where ''C'' is the collection of all [[perfect sets]] of a topological [[Polish space]]. As another example, let ''C'' consist of all the lines of a [[projective plane]], then a [[blocking set]] in this plane is a set of points which intersects each line but contains no line.

==Category theory==