1
$\begingroup$

Suppose that $S_1, S_2, S_3,\ldots, S_n$ are subsets of $\{1,2,\ldots,m\}.$ Let $a_1,a_2,\ldots a_n$ be positive integers such that $|S_i|\geq a_i$ for $1\leq i\leq n,$ $|S_i\cup S_j|\geq a_i+a_j$ for $1\leq i < j\leq n,$... and so on $|S_i\cup S_2\cup\cdots S_n|\geq a_1+a_2+a_3+\cdots +a_n.$ Show that there exists subsets $N_i\subseteq S_i$ for $1\leq i\leq n$ such that $|N_i|=a_i$ for $1\leq i\leq n,$ and $N_i\cap N_j=\emptyset$ for $1\leq i < j\leq n.$

When n=2, if either $|S_1\setminus S_1\cap S_2 |\leq a_1$ (or $|S_2\setminus S_1\cap S_2 |\leq a_2$) we are done as we can choose $N_1\subseteq S_1\setminus S_1\cap S_2$ and $N_2\subseteq S_2.$ Suppose that $|S_1\setminus S_1\cap S_2 |> a_1.$ Let $a_1=|S_1|-|S_1\cap S_2|+r.$ Since $|S_1\cup S_2|\geq a_1+a_2,$ we get $a_2\leq |S_2|-r.$ Thus, we can $N_1=(S_1\setminus S_1\cap S_2)\cup M_0,$ where $M_0\subseteq S_1\cap S_2$ with $|M_0|=r$ and choose $N_2\subseteq S_2\setminus M_0.$ I couldnt extend this for $n\geq3.$

$\endgroup$
5
  • $\begingroup$ Welcome to MSE. In this forum you're expected to show some effort in order to get help. Edit your question to include your work on the problem, otherwise your question will be downvoted and eventually closed. This is not a homework service. $\endgroup$ Commented Oct 15 at 11:42
  • $\begingroup$ Include in your post what you have tried ? $\endgroup$ Commented Oct 15 at 11:43
  • $\begingroup$ A natural start might be to do this for $n=2$. Then try $n=3$. Try to work inductively. $\endgroup$ Commented Oct 15 at 11:44
  • $\begingroup$ You need to check your proof of the case $n=2$. Some inequalities are inverted. $\endgroup$ Commented Oct 15 at 13:03
  • 1
    $\begingroup$ Hint: Hall's marriage theorem. $\endgroup$ Commented Oct 15 at 16:21

1 Answer 1

Reset to default
0
$\begingroup$

This is a consequence of Hall's marriage theorem. Imagine that $\{1,\dots,m\}$ is a set of $m$ men, and that there are disjoint sets $W_1,\dots,W_n$ of women where $|W_i|=a_i$ for each $i$. We stipulate that each woman in $W_i$ is willing to marry any man in $S_i$.

We need to prove that the marriage condition holds. Letting $W\subseteq W_1\cup \dots \cup W_n$ be an arbitrary subset of women, we must show that the set of men considered eligible by some woman in $W$ has at least $|W|$ men. Letting $I\subseteq \{1,\dots,n\}$ be the set of $i$ for which $W_i\cap W$ is nonempty, then the set of men considered eligble by some woman in $W$ is $\bigcup_{i\in I} S_i$, and we have $$ \left|\bigcup_{i\in I}S_i\right|\ge \sum_{i\in I}a_i=\sum_{i\in I}|W_i|\ge |W|, $$ so the marriage condition holds. We can then apply Hall's marriage theorem to assign to each woman a man she is willing to marry. Letting $N_i$ be the set of men married to the women in $W_i$ completes the problem.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer. $\endgroup$ Commented Oct 21 at 4:03

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.