Transversal (combinatorics): Difference between revisions

Revision as of 12:38, 12 April 2015

Latest revision as of 21:36, 19 June 2025

(34 intermediate revisions by 21 users not shown)

Line 1:

{{Short description|Set that intersects every one of a family of sets}}

{{Other uses|Transversal (disambiguation)}}

In [[mathematics]], givenparticularly ain collection[[combinatorics]], ''C''given ofa [[setfamily of theory|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''' (SDR).<ref name="lp">{{Cite Lovasz Plummer}}</ref>{{rp|29}}
* 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, inIn this situation, the members of the '''system of representatives''' are not necessarily distinct.<ref>{{harvnbcitation|last1=Roberts|Tesmanfirst1=Fred S.|title=Applied Combinatorics|year=2009|locedition=pg.2nd|place=Boca 692Raton|publisher=CRC Press|isbn=978-1-4200-9982-9|last2=Tesman|first2=Barry}}</ref>{{Rp|692}}<ref>{{harvnbcitation|last=Brualdi|first=Richard A.|title=Introductory Combinatorics|year=2010|locedition=pg.5th|place=Upper 322Saddle River, NJ|publisher=Prentice Hall|isbn=978-0-13-602040-0}}</ref> {{Rp|322}}

In [[computer science]], computing transversals is useful in several application domains, with the input [[family of sets]] often being described as a [[hypergraph]].

In [[set theory]], the [[axiom of choice]] is equivalent to the statement that every [[partition of a set|partition]] has a transversal.<ref>{{cite web|url=https://plato.stanford.edu/entries/axiom-choice/|title=The Axiom of Choice|website=Stanford Encyclopedia of Philosophy|first=Bell|last=John|date=December 10, 2021|access-date=December 2, 2024|quote=Let us call Zermelo’s 1908 formulation the combinatorial axiom of choice: CAC: Any collection of mutually disjoint nonempty sets has a transversal.}}</ref>

==Existence and number==

A fundamental question in the study of SDR is whether or not an SDR exists. [[Hall's marriage theorem]] gives necessary and sufficient conditions for a finite collection of sets, some possibly overlapping, to have a transversal. The condition is that, for every integer ''k'', every collection of ''k'' sets must contain in common at least ''k'' different elements.<ref name="lp" />{{rp|29}}

*The following refinement by [[H. J. Ryser]] gives lower bounds on the number of such SDRs.<ref>{{citation|last=Ryser|first=Herbert John|author-link=H. J. Ryser|title=Combinatorial Mathematics|year=1963|series=The Carus Mathematical Monographs #14|year=1963|publisher=Mathematical Association of America|author-link=H. J. Ryser}}</ref>{{Rp|48}}

''Theorem''. Let ''S''₁, ''S''₂, ..., ''S''_''m'' be a collection of sets such that <math>S_{i_1} \cup S_{i_2} \cup \dots \cup S_{i_k}</math> contains at least ''k'' elements for ''k'' = 1,2,...,''m'' and for all ''k''-combinations {<math>i_1, i_2, \ldots, i_k</math>} of the integers 1,2,...,''m'' and suppose that each of these sets contains at least ''t'' elements. If ''t'' ≤ ''m'' then the collection has at least ''t'' ! SDRs, and if ''t'' > ''m'' then the collection has at least ''t'' ! / (''t'' - ''m'')! SDRs.

== Relation to matching and covering ==

One can construct a [[bipartite graph]] in which the vertices on one side are the sets, the vertices on the other side are the elements, and the edges connect a set to the elements it contains. Then, a transversal (defined as a system of ''distinct'' representatives) is equivalent to a '''[[perfect matching]]''' in this graph.

One can construct a [[hypergraph]] in which the vertices are the elements, and the hyperedges are the sets. Then, a transversal (defined as a system of ''not-necessarily-distinct'' representatives) is a [[Vertex cover in hypergraphs|'''vertex cover''' in a hypergraph]].

==Examples==

Line 10 ⟶ 31:

In general, since any [[equivalence relation]] on an arbitrary set gives rise to a partition, picking any representative from each [[equivalence class]] results in a transversal.

Another instance of a partition-based transversal occurs when one considers the equivalence relation known as the [[Kernel (set theory)|(set-theoretic) kernel of a function]], defined for a function <math>f</math> with [[Domain of a function|___domain]] ''X'' as the partition of the ___domain <math>\operatorname{ker} f := \left\{\, \left\{\, y \in X \mid f(x)=f(y) \,\right\} \mid x \in X \,\right\}</math>. which partitions the ___domain of ''f'' into equivalence classes such that all elements in a class map via ''f'' to the same value. If ''f'' is injective, there is only one transversal of <math>\operatorname{ker} f</math>. For a not-necessarily-injective ''f'', fixing a transversal ''T'' of <math>\operatorname{ker} f</math> induces a one-to-one correspondence between ''T'' and the [[Image_%28mathematics%29Image (mathematics)#Image_of_a_functionImage of a function|image]] of ''f'', henceforth denoted by <math>\operatorname{Im}f</math>. Consequently, a function <math>g: (\operatorname{Im} f) \to T</math> is well defined by the property that for all ''z'' in <math>\operatorname{Im} f, g(z)=x</math> where ''x'' is the unique element in ''T'' such that <math>f(x)=z</math>; furthermore, ''g'' can be extended (not necessarily in a unique manner) so that it is defined on the whole [[codomain]] of ''f'' by picking arbitrary values for ''g(z)'' when ''z'' is outside the image of ''f''. It is a simple calculation to verify that ''g'' thus defined has the property that <math>f\circ g \circ f = f</math>, which is the proof (when the ___domain and codomain of ''f'' are the same set) that the [[full transformation semigroup]] is a [[regular semigroup]]. <math>g</math> acts as a (not necessarily unique) [[Inverse_element#In_a_semigroup|quasi-inverse]] for ''f''; within semigroup theory this is simply called an inverse. Note however that for an arbitrary ''g'' with the aforementioned property the "dual" equation <math>g \circ f \circ g= g</math> may not hold. However if we denote by <math>h= g \circ f \circ g</math>, then ''f'' is a quasi-inverse of ''h'', i.e. <math>h \circ f \circ h = h</math>.

<!-- this calculation is rather hard to follow without a picture, so I'm not sure it adds much as it is

As a concrete instance, if <math>f: \{1,2,3\} \to \{1,2,3\}</math> is the non-bijective mapping <math>f(1) = 2, f(2)=2, f(3)=3</math>, then its kernel is <math>\operatorname{ker} f = \{ \{1,2\}, \{3\} \}</math>. A transversal of <math>\operatorname{ker} f</math> is <math>T_1 = \{ \{1\}, \{3\} \}</math> and another transversal is <math>T_2 = \{ \{2\}, \{3\} \}</math>. Fixing <math>T_1</math> as the choice of transversal, a function <math>g</math> induced by <math>T_1</math> must have the property that <math>g(2) = 1</math> and <math>g(3) = 3</math>; however the transversal <math>T_1</math> does not constrain where ''g'' maps 1. Nevertheless, it can be verified that ''g'' has the desired quasi-inverse role relative to ''f'': <math>f(g(f(1))) = f(g(2)) = f(1)</math>, <math>f(g(f(2))) = f(g(2)) = f(1) = 2 = f(2)</math>, <math>f(g(f(3))) = f(g(3)) = f(3)</math>. Note that <math>g(1)</math> did not appear in these calculations. One could choose <math>g(1)=2</math>, a choice that makes ''g'' bijective; therefore, we expect that <math>g \circ f \circ g = h \neq g</math>. And indeed <math>h(1) = g(f(g(1)))=1\neq 2 = g(1)</math>. However <math>h(f(h(1)))=h(f(1))=h(2)=g(f(g(2))= g(2)=1</math> is compatible with the role of ''f'' as quasi-inverse of ''h''.

-->

== Common transversals ==

[[Hall's marriage theorem]] gives necessary and sufficient conditions for a finite collection of not necessarily distinct, but non-empty sets to have a transversal.

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>

==Systems of distinct representatives==

A refinement, due to [[H. J. Ryser]], of [[Hall's marriage theorem]] gives lower bounds on the number of systems of distinct representatives ('''SDR'''s) of a collection of sets.<ref>{{harvnb|Ryser|1963|loc=p. 48}}</ref>

''Theorem''. Let ''S''₁, ''S''₂, ..., ''S''_''m'' be a collection of sets such that <math>S_{i_1} \cup S_{i_2} \cup \dots \cup S_{i_k}</math> contains at least ''k'' elements for ''k'' = 1,2,...,''m'' and for all ''k''-combinations {<math>i_1, i_2, \ldots, i_k</math>} of the integers 1,2,...,''m'' and suppose that each of these sets contains at least ''t'' elements. If ''t'' ≤ ''m'' then the collection has at least ''t'' ! SDRs, and if ''t'' > ''m'' then the collection has at least ''t'' ! / (''t'' - ''m'')! SDRs.

== 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''. 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|last=Oxley|first=James G.|title=Matroid Theory|volume=3|page=48|year=2006|series=Oxford graduate texts in mathematics|publisher=Oxford University Press|isbn=978-0-19-920250-8|authorlink=James Oxley}}.</ref>

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.<ref>{{Cite journal|last=Haxell|first=P.|date=2011-11-01|title=On Forming Committees|url=https://www.tandfonline.com/doi/abs/10.4169/amer.math.monthly.118.09.777|journal=The American Mathematical Monthly|volume=118|issue=9|pages=777–788|doi=10.4169/amer.math.monthly.118.09.777|s2cid=27202372 |issn=0002-9890|url-access=subscription}}</ref>

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>

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]]''', 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 set]]s 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.

An example of the latter would be a [[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==

In the language of [[category theory]], a '''transversal''' of a collection of mutually disjoint sets is a [[Section (category theory)|section]] of the [[quotient map]] induced by the collection.

==Computational complexity==

The [[computational complexity]] of computing all transversals of an input [[family of sets]] has been studied, in particular in the framework of [[enumeration algorithm]]s.

==See also==

*[[Axiom of choice]]

*[[Permanent (mathematics)|Permanent]]

==NotesReferences==

{{reflist}}

==ReferencesFurther reading==

* {{citation|last=Brualdi|first=Richard A.|title=Introductory Combinatorics|edition=5th|year=2010|publisher=Prentice Hall|place=Upper Saddle River, NJ |isbn=0-13-602040-2}}

* [[Eugene Lawler|Lawler, E. L.]] Combinatorial Optimization: Networks and Matroids. 1976.

* [[Leon Mirsky|Mirsky, Leon]] (1971). ''Transversal Theory: An account of some aspects of combinatorial mathematics.'' Academic Press. {{ISBN |0-12-498550-5}}.

* {{citation|last1=Roberts|first1=Fred S.|last2=Tesman|first2=Barry|title=Applied Combinatorics|edition=2nd|publisher=CRC Press|place=Boca Raton|year=2009|isbn=978-1-4200-9982-9}}

* {{citation|last=Ryser|first=Herbert John|author-link=H. J. Ryser|title=Combinatorial Mathematics|series=The Carus Mathematical Monographs #14|year=1963|publisher=Mathematical Association of America}}

[[Category:Combinatorics]]

[[Category:Group theory]]

[[Category:Families of sets]]

{{Combin-stub}}