Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-01-12T21:25:30.353Z Has data issue: false hasContentIssue false
  • English
  • Français

Some Generalizations of the Problem of Distinct Representatives

Published online by Cambridge University Press:  20 November 2018

N. S. Mendelsohn  and
A. L. Dulmage
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

If S1, S2, S3, … , Sn are subsets of a set M then it is known that a necessary and sufficient condition that it is possible to choose representatives at such that ai is in Si for (i = 1, 2, 3, … , n) and such that ai ≠ aj for i ≠ j , is that for k = 1, 2, 3, … , n, the union of any k of the sets S1, S2, … , Sn, contains at least k elements. The theorem has a number of consequences amongst which we list the following.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 10 , 1958 , pp. 230 - 241
Copyright
Copyright © Canadian Mathematical Society 1958

References

1. Birkhoff, G., Tres observaciones sobre el algebra lineal, Rev. Univ. Nacional de Tucuman, Ser. A, 5 (1946), 147-150.Google Scholar
2. Dulmage, L. and Halperin, I., On a theorem of Frobenius-König and J. von Neumann's game of hide and seek, Trans. Roy. Soc. Can., Ser. III, 49 (1955), 23-29.Google Scholar
3. Everett, C. J. and Whaples, G., Representations of sequences of sets, Amer. J. Math., 71 (1949), 287-293.Google Scholar
4. Frobenius, G., Ueber matrizen mit nicht negativen elementen, S. B. Berliner Akad., 23 (1912), 456-477.Google Scholar
5. Hall, M., An existence theorem for latin squares, Bull. Amer. Math. Soc, 51 (1945), 387-388.Google Scholar
6. Hall, M., Distinct representatives of subsets, Bull. Amer. Math. Soc., 54 (1948), 922-926.Google Scholar
7. Hall, P., On representatives of subsets, J. Lond. Math. Soc, 10 (1935), 26-30.Google Scholar
8. Halmos, P. R. and Vaughan, H. E., The marriage problem, Amer. J. Math., 72 (1950), 214-215.Google Scholar
9. Hoffman, A. J. and Kuhn, H. W., Systems of Distinct representatives and linear programming, Amer. Math. Monthly, 63 (1956), 455-460.Google Scholar
10. Hoffman, A. J. and Wielandt, H. W., The variation of the spectrum of a normal matrix, Duke Math. J., 20 (1953), 37–39.Google Scholar
11. König, D., Ueber Graphen una ihre anwendung, Math. Ann., 77 (1916), 453-465.Google Scholar
12. König, D., Theorie der endlichen und unendlichen graphen (Chelsea, New York, 1950), 170– 178.Google Scholar
13. Maak, W., Eine neue definition der fastperiodicshen functionen, Abh. Math. Sem. Hamb., 11 (1936), 240-244.Google Scholar
14. Mann, H. B., Analysis and design of experiments (Dover, New York, 1949).Google Scholar
15. Mann, H. B., and Ryser, H. J., Systems of distinct representatives, Amer. Math. Monthly, 60 (1953), 397-401.Google Scholar
16. von Neumann, J., A certain zero-sum two person game equivalent to the optimal assignment problem, Contribution to the theory of games II, Ann. Math. Studies, no. 28 (1950), 5–12.Google Scholar
17. Rado, R., Bemerkungen zur kombinatorik im anschluss an untersuchen von herrn D. König, Setz. Ber. Math. Geselt, 32 (1933), 60-75.Google Scholar
18. Ryser, H. J., A combinatorial theorem with an application to latin rectangles, Proc. Amer. Math. Soc, 2 (1951), 550-552.Google Scholar
19. Smith, C. A. B. and Hartley, H. O., The construction of Youden squares, J. Roy. Statist. Soc, Ser. B, 10 (1948), 262-263.Google Scholar
20. Sperner, E., Note zu der arbeit von herrn B.L. von der Waerden: ein satz ueber klasseneinteilungen von endlichen mengen, Abh. Math. Sem. Hamb., 5 (1926), 232.Google Scholar
21. von der Waerden, B. L., Ein satz ueber klasseneinteilungen von endlichen mengen, Abh. Math. Sem. Hamb., 5 (1926), 185-188.Google Scholar
22. Weyl, H., Almost periodic invariant vector sets in a metric vector space, Amer. J. Math., 71 (1949), 178-205.Google Scholar