Geodesic
On Existence of Distinct Representative Sets for Subsets of a Finite Set
Canadian journal of mathematics, Tome 22 (1970) no. 6, pp. 1284-1292

Voir la notice de l'article provenant de la source Cambridge University Press

Let S be a finite set and let S 1, S 2, ..., St be subsets of S, not necessarily distinct. Does there exist a set of distinct representatives (SDR) for S 1, S 2, ..., St ? That is, does there exist a subset {a 1, a 2, ..., 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 S 1, S 2, ..., St have an SDR if and only if for each s, 1 ≦ s ≦ t, |S i1 ∪ S i1 ∪ ... ∪ Sis | ≧ s for each s-comhination {i 1, i 2, ..., is } of the integers 1, 2, ..., t.(Here and below, |A| denotes the number of elements in A.) 
Clements, G. F. On Existence of Distinct Representative Sets for Subsets of a Finite Set. Canadian journal of mathematics, Tome 22 (1970) no. 6, pp. 1284-1292. doi: 10.4153/CJM-1970-144-8
@article{10_4153_CJM_1970_144_8,
     author = {Clements, G. F.},
     title = {On {Existence} of {Distinct} {Representative} {Sets} for {Subsets} of a {Finite} {Set}},
     journal = {Canadian journal of mathematics},
     pages = {1284--1292},
     year = {1970},
     volume = {22},
     number = {6},
     doi = {10.4153/CJM-1970-144-8},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1970-144-8/}
}
TY  - JOUR
AU  - Clements, G. F.
TI  - On Existence of Distinct Representative Sets for Subsets of a Finite Set
JO  - Canadian journal of mathematics
PY  - 1970
SP  - 1284
EP  - 1292
VL  - 22
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1970-144-8/
DO  - 10.4153/CJM-1970-144-8
ID  - 10_4153_CJM_1970_144_8
ER  - 
%0 Journal Article
%A Clements, G. F.
%T On Existence of Distinct Representative Sets for Subsets of a Finite Set
%J Canadian journal of mathematics
%D 1970
%P 1284-1292
%V 22
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1970-144-8/
%R 10.4153/CJM-1970-144-8
%F 10_4153_CJM_1970_144_8

[1] 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] 2. Hall, P., On representatives of subsets, J. London Math. Soc. 10 (1935), 26–30. Google Scholar

[3] 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] 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] 5. Riordan, J., An introduction to combinatorial analysis (Wiley, New York, 1958). Google Scholar

[6] 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

Cité par Sources :