Transversal (combinatorics): Difference between revisions

Revision as of 08:53, 4 August 2020

Revision as of 09:12, 4 August 2020

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''' (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>{{harvnb|Roberts|Tesman|2009|loc=pg. 692}}</ref><ref>{{harvnb|Brualdi|2010|loc=pg. 322}}</ref>

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

==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 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}}

AThe following refinement, due toby [[H. J. Ryser]], of [[Hall's marriage theorem]] gives lower bounds on the number of systems of distinct representatives ('''SDR'''s) of a collection ofsuch setsSDRs.<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.

== 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 is equivalent to a [[Perfect matching|'''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 is equivalent to a [[Vertex cover in hypergraphs|'''vertex cover''' in a hypergraph]].

==Examples==

Line 14 ⟶ 32:

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''.

-->

[[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.

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

==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.

== Common Transversals ==