Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-26T00:32:56.314Z Has data issue: false hasContentIssue false
  • English
  • Français

On Existence of Distinct Representative Sets for Subsets of a Finite Set

Published online by Cambridge University Press:  20 November 2018

G. F. Clements
G. F. Clements*
Affiliation:
University of Colorado, Boulder, Colorado
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.

Let S be a finite set and let S1, S2, …, St be subsets of S, not necessarily distinct. Does there exist a set of distinct representatives (SDR) for S1, S2, …, St? That is, does there exist a subset {a1, a2, …, at} of S such that ai ∊ Si, 1 ≦ i ≦ t, and ai ≠ aj if i ≠ j? The following theorem of Hall [2; 6, p. 48] gives the answer.

THEOREM. The subsets S1, S2, …, St have an SDR if and only if for each s, 1 ≦ s ≦ t, |Si1 ∪ Si1 ∪ … ∪ Sis| ≧ s for each s-comhination {i1, i2, …, is} of the integers 1, 2, …, t.

(Here and below, |A| denotes the number of elements in A.)

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 22 , Issue 6 , 01 December 1970 , pp. 1284 - 1292
Copyright
Copyright © Canadian Mathematical Society 1970

References

1. Clements, G. F. and Lindström, B., A generalization of a combinatorial theorem of Macaulay, J. Combinatorial Theory 7 (1969), 230–238.Google Scholar
2. Hall, P., On representatives of subsets, J. London Math. Soc. 10 (1935), 26–30.Google Scholar
3. Katona, G., A theorem of finite sets, pp. 187-207 in Theory of graphs, Proceedings of the colloquium held at Tihany, Hungary, September, 1966; edited by Erdös, P. and Katona, G. (Academic Press, New York-London, 1968).Google Scholar
4. Macaulay, F. S., Some properties of enumeration in the theory of modular systems, Proc London Math. Soc. (2) 26 (1927), 531–555.Google Scholar
5. Riordan, J., An introduction to combinatorial analysis (Wiley, New York, 1958).Google Scholar
6. Ryser, H. J., Combinatorial mathematics, The Carus Mathematical Monographs, No. 14 (The Mathematical Association of America; distributed by John Wiley, New York, 1963).Google Scholar