Problem of selection from overlapping sets

Question

For a positive integer $m$, let $A_1,\ldots,A_m$ be (not necessarily disjoint and potentially empty) finite sets and let $c_1,\ldots,c_m$ be non-negative integers. Suppose that

• each set $A_i$ contains at least $c_i$ elements; and
• the union $\bigcup_{i=1}^m A_i$ contains precisely $\sum_{i=1}^m c_i$ elements.

Intuitively, it should be possible to choose precisely $c_i$ elements from each $A_i$ in such a way that no element is picked twice. Formally, what I want to prove is that there exist sets $(B_i)_{i=1}^m$ such that

• $B_i\subseteq A_i$ for each $i$;
• the cardinality of $B_i$ is precisely $c_i$ for each $i$; and
• $B_i\cap B_j=\varnothing$ for $i\neq j$.

I tried induction on the number of sets. The case $m=2$ is pretty straightforward. (Assign $A_1\setminus A_2$ to $B_1$, assign $A_2\setminus A_1$ to $B_2$, and divvy up $A_1\cap A_2$ between $B_1$ and $B_2$; this can be done in the desired way, so that $\#B_1=c_1$ and $\#B_2=c_2$.) But then I got stuck with having the induction hypothesis carry over.

In particular, the main difficulty is that if $\bigcup_{i=1}^{m+1}A_i$ contains $\sum_{i=1}^{m+1} c_i$ elements, this does not necessarily imply that the smaller union $\bigcup_{i=1}^{m}A_i$ contains precisely $\sum_{i=1}^{m} c_i$ elements, as the sets are not necessarily disjoint. This makes the inductive proof more difficult, and a non-inductive proof (relying on, say, inclusion–exclusion) seems prohibitively complicated.

I am hoping that someone reading this may have an ingenious shortcut in mind as to how to make the induction hypothesis go through.

Answer 1

This need not be true.

EG Take $ c_ 1 = c_2 = c_3 = 1, A_1 = \{a\}, A_2 = \{a\}, A_3 = \{a, b, c \}$.

---

For a more elaborate answer, apply Hall Marriage Theorem to the bipartite graph $G ( X + Y , E )$, where

• $ X $ is the multi set $\{ c_i \cdot A_i\} $ (Total $\sum c_i$ of them)
• $Y $ are the elements of the base set (Total $ \sum c_i$ of them)
• $E$ is the edge where element $ y$ is in set $A_i$.

A solution to the original problem is a perfect matching of this bipartite graph.

Apply Hall Marriage theorem, we know that a perfect matching exists iff for each subfamily $ W $, the connected vertices satisfy $|W| \leq | N_G (W) |$ .
This is true for the singletons $A_i$ by the definitions.
However, if sets $A_1, A_2$ have a high overlap, then it is possible that $ |\{ A_1, A_2 \} | > |N_G (\{ A_1, A_2 \} ) |$. Hence, we should be able to find a counter example here.