Two inequalities with inclusion-exclusion

Question

Let $S$ be a base set of size $n$. Also denote $k$ of $S$'s subsets by $A_1,...,A_k\in 2^S$ such that $\bigcup_i A_i=S$. Furthermore, let $n_\alpha=\lvert\bigcap_{i\in\alpha}A_i\rvert$ be the size of the intersection of sets in the index set $\alpha\subset I=\{1,...,k\}$. For example, $n_{1,3,4}=\lvert A_1\cap A_3\cap A_4\rvert$ if $k\ge4$.

We know that $\forall i\in I: n_i\ge3$ and $\sum_i n_i>\sum_{\alpha\subset I} (-1)^{\lvert\alpha\rvert+1}{n_\alpha\choose2}$.

If I could show that $\sum_{\alpha\subset I} (-1)^{\lvert\alpha\rvert+1}n_\alpha\le2k$, that would help me a lot with my project.

I have tried an inductive proof but got stuck. I have also tried to represent the task with two lattices (or semi-lattices, I am not sure) and find some mapping there but that failed too. I have checked Richard Stanley's book on Enumerative Combinatorics but I did not see anything that would connect inclusion-exclusion sums of numbers and binomial coefficients.

I would be very grateful for any ideas. Thank you.

Answer 1

We will adopt the convention that the empty intersection $\bigcap_{i\in\varnothing} A_i$ is $S$ (which is natural because $S$ is the identity of the intersection operator on the algebra of sets over $S$.) Also, we will use the indicator function notation

$$ \mathbf{1}_A (x) = \begin{cases} 1, & x \in A, \\ 0, & x \notin A. \end{cases} $$

This is convenient, because for each $\alpha \subseteq I$ we have

$$ n_{\alpha} = \left| \bigcap_{i \in \alpha} A_i \right| = \sum_{x\in S} \mathbf{1}_{\bigcap_{i \in \alpha} A_i}(x) = \sum_{x\in S} \prod_{i\in\alpha} \mathbf{1}_{A_i}(x). $$

Then

\begin{align*} \sum_{\alpha \subseteq I} (-1)^{|\alpha|+1} n_{\alpha} &= \sum_{\alpha \subseteq I} (-1)^{|\alpha|+1} \sum_{x\in S} \prod_{i\in\alpha} \mathbf{1}_{A_i}(x) \\ &= - \sum_{x\in S} \sum_{\alpha \subseteq I} \prod_{i\in\alpha} \bigl(-\mathbf{1}_{A_i}(x) \bigr) \\ &= - \sum_{x\in S} \prod_{i\in I} \bigl(1-\mathbf{1}_{A_i}(x) \bigr) \\ &= - \sum_{x\in S} \prod_{i\in I} \mathbf{1}_{S \setminus A_i}(x) \\ &= - \sum_{x\in S} \mathbf{1}_{S \setminus \bigcup_{i\in I} A_i}(x) \\ &= - \left| S \setminus {\textstyle \bigcup_{i\in I} A_i} \right|. \end{align*}

Note that this formula is valid for any finite family of subsets $\{A_i\}_{i\in I}$ of $S$. Now, OP's condition tells that $\bigcup_{i\in I} A_i = S$. Therefore, we always have

$$ \sum_{\alpha \subseteq I} (-1)^{|\alpha|+1} n_{\alpha} = 0 $$

regardless of all the other conditions imposed.

Example. Consider $S = \{1,2,3,4,5,6\}$ and \begin{align*} A_1 &= \{2, 4, 6\}, & A_2 &= \{2, 3, 5, 6\}, \\ A_3 &= \{1, 2, 3, 4, 5\}, & A_4 &= \{2, 3, 4, 5, 6\}. \end{align*} Clearly, $\bigcup_{i=1}^{4} A_i = S$. Also, \begin{align*} n_{\varnothing} &= |\{1, 2, 3, 4, 5, 6\}| = 6, & n_{\{1\}} &= |\{2, 4, 6\}| = 3, \\ n_{\{2\}} &= |\{2, 3, 5, 6\}| = 4, & n_{\{3\}} &= |\{1, 2, 3, 4, 5\}| = 5, \\ n_{\{4\}} &= |\{2, 3, 4, 5, 6\}| = 5, & n_{\{1, 2\}} &= |\{2, 6\}| = 2, \\ n_{\{1, 3\}} &= |\{2, 4\}| = 2, & n_{\{1, 4\}} &= |\{2, 4, 6\}| = 3, \\ n_{\{2, 3\}} &= |\{2, 3, 5\}| = 3, & n_{\{2, 4\}} &= |\{2, 3, 5, 6\}| = 4, \\ n_{\{3, 4\}} &= |\{2, 3, 4, 5\}| = 4, & n_{\{1, 2, 3\}} &= |\{2\}| = 1, \\ n_{\{1, 2, 4\}} &= |\{2, 6\}| = 2, & n_{\{1, 3, 4\}} &= |\{2, 4\}| = 2, \\ n_{\{2, 3, 4\}} &= |\{2, 3, 5\}| = 3, & n_{\{1, 2, 3, 4\}} &= |\{2\}| = 1. \end{align*} (We can also check that $\{A_1, A_2, A_3, A_4\}$ satisfies all the other conditions imposed by OP. However, they are not relevant to the computation below.) So, \begin{align*} &\sum_{\alpha \subseteq I} (-1)^{|\alpha|+1} n_{\alpha} \\ &= (-1)^{0+1} \cdot 6 + (-1)^{1+1} \cdot 3 + (-1)^{1+1} \cdot 4 + (-1)^{1+1} \cdot 5 + (-1)^{1+1} \cdot 5 \\ &\quad + (-1)^{2+1} \cdot 2 + (-1)^{2+1} \cdot 2 + (-1)^{2+1} \cdot 3 + (-1)^{2+1} \cdot 3 + (-1)^{2+1} \cdot 4 + (-1)^{2+1} \cdot 4 \\ &\quad + (-1)^{3+1} \cdot 1 + (-1)^{3+1} \cdot 2 + (-1)^{3+1} \cdot 2 + (-1)^{3+1} \cdot 3 + (-1)^{4+1} \cdot 1 \\ &= 0. \end{align*}

Answer 2

For $r=0,1,\dots,k$ let $U_{r}$ denote the set of elements that have exactly $r$ occurrences in the $A_{i}$; so actually: $$x\in U_r\iff\sum_{i=1}^k1_{A_i}(x)=r$$ Then:

$$1_{U_{r}}=\sum_{\alpha\subseteq I}\binom{\left|\alpha\right|}{r}\left(-1\right)^{\left|\alpha\right|-r}1_{\bigcap_{i\in\alpha}A_{i}}\tag1$$

and consequently: $$\left|U_{r}\right|=\sum_{\alpha\subseteq I}\binom{\left|\alpha\right|}{r}\left(-1\right)^{\left|\alpha\right|-r}n_{\alpha}\tag2$$ This under the convention that a binomial coefficient $\binom{m}s$ takes value $0$ if $s\notin\{0,\dots,m\}$.

In your case we have $S=\bigcup_{i=1}^kA_i$ so that every element has an occurrence in at least one of the $A_{i}$.

That means that $U_{0}=\varnothing$ and consequently:

$$0=\left|U_{0}\right|=\sum_{\alpha\subseteq I}\binom{\left|\alpha\right|}{0}\left(-1\right)^{\left|\alpha\right|}n_{\alpha}=\sum_{\alpha\subseteq I}\left(-1\right)^{\left|\alpha\right|}n_{\alpha}$$

---

If you are interested in a proof of $(1)$ then please let me know.