Transversal (combinatorics): Difference between revisions

Revision as of 15:36, 22 April 2021

Latest revision as of 21:36, 19 June 2025

(10 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|A lineSet that intersects every one of a systemfamily of lines.sets}}

{{Other uses|Transversal (disambiguation)}}

Line 5:

* 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>{{citation|last1=Roberts|first1=Fred S.|title=Applied Combinatorics|year=2009|edition=2nd|place=Boca Raton|publisher=CRC Press|isbn=978-1-4200-9982-9|last2=Tesman|first2=Barry}}</ref>{{Rp|692}}<ref>{{citation|last=Brualdi|first=Richard A.|title=Introductory Combinatorics|year=2010|edition=5th|place=Upper Saddle River, NJ|publisher=Prentice Hall|isbn=978-0-13-602040-20}}</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|title=Combinatorial Mathematics|year=1963|series=The Carus Mathematical Monographs #14|publisher=Mathematical Association of America|author-link=H. J. Ryser}}</ref>{{Rp|48}}

Line 34 ⟶ 36:

-->

== Common Transversalstransversals ==

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

Line 42 ⟶ 44:

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>

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 setsset]]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.

==Category theory==

Line 65 ⟶ 67:

[[Category:Combinatorics]]

[[Category:Group theory]]

[[Category:SetFamilies familiesof sets]]