Content deleted Content added
m Disambiguating links to Permanent (link changed to Permanent (mathematics)) using DisamAssist. |
Common transversals |
||
Line 22:
''Theorem''. Let ''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>''m''</sub> 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 ==
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 |year=1974 |pages=161}}</ref>
== Generalizations ==
| |||