Is there a generalized upper bound for $\sum_{i = 1}^n | X \cap D_i |$ for $n > 2$?

Question

Let $D_1, ..., D_n$ be arbitrary $n$ sets where $D_i \cap D_j \neq \emptyset$. In the simplified case where $n = 2$, we have that $$ \begin{split} | X \cap D_1 | + | X \cap D_2 | = &| X \cap (D_1 \setminus D_2) | + | X \cap (D_1 \cap D_2) | \\ &+ | X \cap (D_2 \setminus D_1) | + | X \cap (D_1 \cap D_2) | \\ = & |X| + | X \cap (D_1 \cap D_2) | \\ \leq & |X| + | D_1 \cap D_2 |. \end{split} $$

My question is that, can we generalize the above upper bound to something like $$ \sum_{i = 1}^n | X \cap D_i | \leq |X| + c, $$ where $c$ is dependent on $(D_1, D_2, ..., D_n)$? It is self-evident that, if $D_1, ..., D_n$ is a disjoint partition of a universe, then we have $\sum_{i = 1}^n | X \cap D_i | = |X|$. However, it seems difficult for me to bound $c$ when $D_1, ..., D_n$ are not disjoint.

It would be appreciated if you could give me any hint.

Answer 1

Yes, the generalised statement follows from a centerpiece of combinatorics, known as the Inclusion-Exclusion Princinple (see the page for a full answer).

It gives you a sequence of upper and lower bounds for the number of elements in a union of sets. In particular, your summation is exactly the 'second order' part of the inclusion-exclusion principle formula.

For for a hint, try this: If $X = \bigcup_{i=1}^n D_i$, try express $|X|$ in terms of the terms $\sum|D_i|$, $\sum|D_i \cap D_j|$, $\sum |D_i\cap D_j \cap D_k|$ and so on.

Answer 2

Following Brandons answer, what I would use for an upper bound of similar efficiency (In the spirit of sieve techniques) would be:

$$\sum_{i = 1}^n | X \cap D_i | \leq |X| + n/2\cdot(n-1)\cdot \max_{i\neq j}(|D_i\cap D_j|),$$

This is the truncated sum, and if you can control the size of intersections, and $n$ is relatively small compared to $|X|$ this can yield a good estimate.