Transversal (combinatorics): Difference between revisions

Revision as of 15:51, 22 April 2021

Revision as of 17:16, 30 December 2021

Line 11:

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