1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Are you familiar with Hall Marriage Theorem? $\endgroup$
    – Calvin Lin
    Nov 13, 2021 at 18:38

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$
    – triple_sec
    Nov 13, 2021 at 18:44

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.