# Problem of selection from overlapping sets

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.

• Are you familiar with Hall Marriage Theorem? Nov 13, 2021 at 18:38

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.

• Thank you very much! Nov 13, 2021 at 18:44