Content deleted Content added
+link to hypergraph, +link to enumeration algorithms |
No edit summary |
||
Line 1:
{{Other uses|Transversal (disambiguation)}}
In [[mathematics]], particularly in [[combinatorics]], given a [[family of sets]], here called a collection ''C'', a '''transversal''' (also called a '''cross-section'''<ref name="Howie1995">{{cite book|author=John Mackintosh Howie|authorlink = John Mackintosh Howie|title=Fundamentals of Semigroup Theory|year=1995|publisher=Clarendon Press|isbn=978-0-19-851194-6|page=63}}</ref><ref name="Reis2011">{{cite book|author=Clive Reis|title=Abstract Algebra: An Introduction to Groups, Rings and Fields|year=2011|publisher=World Scientific|isbn=978-981-4335-64-5|page=57}}</ref><ref name="CourcelleEngelfriet2012">{{cite book|author1=Bruno Courcelle|author1link = Bruno Courcelle|author2=Joost Engelfriet|title=Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach|year=2012|publisher=Cambridge University Press|isbn=978-1-139-64400-6|page=95}}</ref>) is a set containing exactly one element from each member of the collection. When the sets of the collection are mutually disjoint, each element of the transversal corresponds to exactly one member of ''C'' (the set it is a member of). If the original sets are not disjoint, there are two possibilities for the definition of a transversal. One variation, the one that mimics the situation when the sets are mutually disjoint, 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. In this case, the transversal is also called a '''system of distinct representatives'''. The other, less commonly used, possibility does not require a one-to-one relation between the elements of the transversal and the sets of ''C''. Loosely speaking, in this situation the members of the ''system of representatives'' are not necessarily distinct.<ref>{{harvnb|Roberts|Tesman|2009|loc=pg. 692}}</ref><ref>{{harvnb|Brualdi|2010|loc=pg. 322}}</ref>
==Examples==
Line 28:
A '''common transversal''' of the collections ''A'' and ''B'' (where <math>|A| = |B| = n</math>) is a set that is a transversal of both ''A'' and ''B''. The collections ''A'' and ''B'' have a common transversal if and only if, for all <math>I, J \subset \{1,...,n\}</math>,
:<math>|(\bigcup_{i \in I}A_i) \cap (\bigcup_{j \in J}B_j)| \geq |I|+|J|-n</math><ref name="Milner1974">{{citation |title=TRANSVERSAL THEORY, Proceedings of the international congress of mathematicians |author=E. C. Milner |authorlink = Eric Charles Milner|year=1974 |pages=161}}</ref>
== Generalizations ==
| |||