Existence of “sufficiently rich” unions Let $m$ be a positive integer and define $M\equiv\{1,\ldots,m\}$. Let $A_1,\ldots,A_m$ be (not necessarily disjoint and potentially empty) finite sets. Moreover, let $c_1,\ldots,c_m$ be non-negative integers. For each $i\in M$, $A_i$ may or may not contain precisely $c_i$ elements, but assume that the following is true (here, $\#$ denotes cardinality): $$\#\left(\bigcup_{i\in M} A_i\right)=\sum_{i\in M}c_i.$$

Conjecture: There exists a non-empty index subset $T^*\subseteq M$ with the following properties:

*

*$\#\left(\bigcup_{i\in T} A_i\right)\geq\sum_{i\in T}c_i$ whenever $T\subseteq T^*$; and

*$\#\left(\bigcup_{i\in T} A_i\right)\geq\sum_{i\in T}c_i$ whenever $T\supseteq T^*$.


In words, I am looking to establish the existence of an index set $T^*$ such that if the index set $T$ is either a subset or a superset of $T^*$, then the union of the $A_i$’s over $T$ contains at least as many elements as the sum of the $c_i$’s over $T$.
Any references to a proof or hints about a counterexample would be appreciated.

UPDATE: Cases for a small number of sets are simple enough to be checked “manually.” When $m=1$ or $m=2$, the conjecture is trivial and very easy, respectively, to prove. When $m=3$, a systematic analysis of all seven ($2^3-1$) non-empty subsets of $\{1,2,3\}$ reveals that the conjecture holds true as well. I am still struggling to come up with a proof or counterexample when $m\geq 4$.
 A: For each $k\in M$, let $B_k=A_k\setminus\bigcup_{i<k}A_i$. Then we have $$\#\left(\bigcup_{i\in T}B_i\right)\leqslant \#\left(\bigcup_{i\in T}A_i\right)$$ for every $T\subseteq M$, so to find a subset $T^*\subseteq M$ that has the desired properties with respect to the $A_i$ it suffices to find one that has the desired properties with respect to the $B_i$. Note that the $B_i$ are pairwise disjoint.
Now, let $T^*\subseteq M$ be the set $\{i\in M:\#B_i\geqslant c_i\}$. Certainly $T^*$ is non-empty, since otherwise $\#B_i<c_i$ for every $i\in M$, contradicting that $$\#\left(\bigcup_{i\in M}B_i\right)=\#\left(\bigcup_{i\in M}A_i\right)=\sum_{i\in M}c_i.$$
I claim that $T^*$ has the desired property. For the first bullet point, suppose $T\subseteq T^*$. Then $$\#\left(\bigcup_{i\in T}B_i\right)=\sum_{i\in T}\#B_i\geqslant \sum_{i\in T}c_i,$$ as desired, where the first equality follows from pairwise disjointness of the $B_i$ and the second follows from definition of $T^*$.
For the second bullet point, suppose $T^*$ does not have that property, and let $T\supseteq T^*$ be a counterexample. Then $\#\left(\bigcup_{i\in T}B_i\right)<\sum_{i\in T}c_i$ On the other hand, by definition of $T^*$, and since $T\supseteq T^*$, we have $\#B_i<c_i$ for every $i\in M\setminus T$. In particular, $\#\left(\bigcup_{i\in M\setminus T}B_i\right)\leqslant\sum_{i\in M\setminus T}c_i$, with equality holding only if $M\setminus T=\varnothing$. So now
\begin{align}\#\left(\bigcup_{i\in M}B_i\right)&=\#\left(\bigcup_{i\in T}B_i\right)+\#\left(\bigcup_{i\in M\setminus T}B_i\right) \\
&<\sum_{i\in T}c_i+\sum_{i\in M\setminus T}c_i \\
&=\sum_{i\in M}c_i,
\end{align} a contradiction. So we are done.
