Transversal (combinatorics): Difference between revisions

Revision as of 09:12, 4 August 2020

Revision as of 09:16, 4 August 2020

Line 4:

* One variation 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, does not require a one-to-one relation between the elements of the transversal and the sets of ''C''. In 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=0-13-602040-2}}</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]].

Line 12:

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

The following refinement by [[H. J. Ryser]] gives lower bounds on the number of such SDRs.<ref>{{harvnbcitation|last=Ryser|first=Herbert John|title=Combinatorial Mathematics|year=1963|locseries=pThe Carus Mathematical Monographs #14|publisher=Mathematical Association of America|author-link=H. 48J. 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.

Line 55:

*[[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]]