Let $A=\{A_1,….A_n\}$ be a collection of subsets of a finite set $X$. A selection for $A$ is the image of an injective function $f:A\to X$ such that $ f(A_i)\in A_i$ for every $A_i\in A$.
Hall's marriage theorem shows that , $A$ has a selection if and only if for each subset $S\subseteq A$,
$$|S|\leq |\cup_{i\in S} A_i|.$$
I wonder if it is possible to generalize this result and obtain a similar condition for a choice correspondence $f:A\rightrightarrows X $ that selects for each $A_i$ more than one elements, i.e. $f(A_i)\subset A_i$ and $|f(A_i)|=2$ and all selected elements are distinct.
Any ideas or suggestions?
Best Answer
Yes, this is a straightforward extension. Instead of the sequence $$A_1,A_2,\ldots,A_n$$ consider the sequence $$A_1,A_1,A_2,A_2,\ldots,A_n,A_n.$$ The Hall condition for this sequence amounts to $$\left|\bigcup_{i\in S}A_i\right|\ge2|S|.$$