2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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|.$$

$\endgroup$
  • $\begingroup$ Great. Thanks for your answer! $\endgroup$ – sam Nov 30 '18 at 5:27
  • $\begingroup$ @sam This doesn't work very well with your (incorrect) definition of a choice function. You should define a choice function as an injection $f:\{1,2,\dots,n\}\to X$ instead of an injection $f:\{A_1,A_2,\dots,A_n\}\to X$ for just this reason, that you don't want to require the sets $A_i$ to be distinct. $\endgroup$ – bof Nov 30 '18 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.