On Existence of Distinct Representative Sets for Subsets of a Finite Set
- 1 December 1970
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 22 (6) , 1284-1292
- https://doi.org/10.4153/cjm-1970-144-8
Abstract
LetSbe a finite set and letS1,S2, …,Stbe subsets ofS,not necessarily distinct. Does there exist a set of distinct representatives (SDR) forS1,S2, …,St? That is, does there exist a subset {a1,a2, …,at} ofSsuch thatai∊Si, 1 ≦i≦t, andai≠ajifi≠j? The following theorem of Hall [2;6, p. 48] gives the answer.THEOREM.The subsets S1,S2, …,Sthave an SDR if and only if for each s,1 ≦s≦t, |Si1∪Si1∪ … ∪Sis| ≧sfor eachs-comhination {i1,i2, …,is}of the integers1, 2, …,t.(Here and below, |A| denotes the number of elements inA.)Keywords
This publication has 0 references indexed in Scilit: