Relation between inclusion-exclusion principle and maximum-minimums identity

Question

Inclusion-exclusion principle states that the size of the union of $n$ finite sets is given by the sum of the sizes of all sets minus sum of the sizes of all the pairwise intersections plus sum of the sizes of all the triple intersections and so on: $$ \left| A_1\cup \dots \cup A_n\right| = \sum_i \left| A_i\right|-\sum_{i<j} \left| A_i\cap A_j\right|+\sum_{i<j<k} \left| A_i\cap A_j\cap A_k\right|-\dots+(-1)^{n+1}\left| A_1\cap \dots \cap A_n\right|. $$ Maximum-minimums identity states that the maximum of a finite set of numbers $S = \{x_1, \dots, x_n \}$ is given by the sum of all elements minus the sum of minimums of all pairs of elements plus sum of minimums of all triples and so on: $$ \max\{x_1, \dots,x_n\} = \sum_i x_i -\sum_{i<j}\min\{x_i, x_j\} + \sum_{i<j<k}\min\{x_i, x_j,x_k\}-\dots+(-1)^{n+1}\min\{x_1,\dots, x_n\}. $$ It is hard to miss the similarity.

1. Is there a relation between maximum-minimums identity and inclusion-exclusion principle?
2. Can either one be proven from the other?

Answer 1

From inclusion-exclusion you can derive the maximums-minimums result, and I'd be surprised if the other direction doesn't hold, either.

In the following I take the inclusion-exclusion formula to be about probabilities, with $P(A_i\cap A_j)$ and so on for events $A_i$ and $A_j$, instead of cardinalities $|A_i\cap A_j|$ of finite sets. One can convert the one formulation into the other by dividing; both can be proved by integrating expressions involving characteristic functions like $\chi_{A\cap B}(x) = \chi_A(x) \chi_B(x)$ against counting measure or against an arbitrary probability measure. The trick is that $\chi_{\bigcup A_i}(x) = 1- \prod_i (1-\chi_{A_i}(x)).$

Assume, in the max-min problem, that the $x_i$ all lie in $[0,1]$ and are sorted in increasing order. (You can add or subtract a constant to all the $x_i$ without spoiling the equation, similarly rescale them, similarly permute them.) Now let $U$ be a uniform random variable, and let $A_i$ be the event that $U\le x_i$. If $i<j$ we have $A_i\cap A_j=A_i$ so $P(A_i\cap A_j) = \min(x_i,x_j)$, and so on. The event $A_1\cup\cdots \cup A_n$ is simply $A_n$, whose probability is $x_n=\max(x_1,\dots,x_n)$. In this way the two identities agree, term by term.

Answer 2

Inspired by kimchi lover's proof:

Let us first assume $x_1,\dots,x_n$ are positive integers. Then we can construct sets $A_i = \{1, \dots, x_i\}$ for all $i$s. Now $|A_i|=x_i$, therefore, $|A_1\cup\dots\cup A_n|=\max\{x_1,\dots,x_n\}$, $|A_i\cap A_j|=\min\{x_i,x_j\}$, and so on.

We can extend this proof to the case where $x_i$s can be negative by shifting all the elements, finding the maximum and then shifting back.

Similarly, we can extend to rationals by multiplying everything by the common denominator.

Finally, we can extend to reals by continuity.

Answer 3

I think we can pull the proof in the other direction fairly easily. Let $x\in S$ and let:

$$x_i=\begin{cases}1, & x\in A_i \\ 0, & \text{otherwise}\end{cases}$$

(The value of the indicator function of the set $A_i$ on $x$.) Now, for each $x\in S$, write one equality of the form:

$$ \max\{x_1, \dots,x_n\} = \sum_i x_i -\sum_{i<j}\min\{x_i, x_j\} + \sum_{i<j<k}\min\{x_i, x_j,x_k\}-\dots+(-1)^{n+1}\min\{x_1,\dots, x_n\} $$

Then, sum them over all $s\in S$. The result will give the inclusion-exclusion principle identity.

Answer 4

Without loss of generality, reindex the elements so that $i\lt j\implies x_i\le x_j$. Let $U_k$ be the set of $k$-tuples from $\{x_j:1\le j\le n\}$ $$ U_k=\{(x_{j_1},x_{j_2},\dots,x_{j_k}):1\le j_1\lt j_2\lt\dots\lt j_k\le n\} $$ Note that $|U_k|=\binom{n}{k}$.

$x_j$ is the minimum in $\binom{n-j}{k-1}$ elements of $U_k$. Therefore, $$ \sum_{u\in U_k}\min u=\sum_{j=1}^n x_j\binom{n-j}{k-1} $$ and so $$ \begin{align} \sum_{k=1}^n(-1)^{k-1}\sum_{u\in U_k}\min u &=\sum_{k=1}^n(-1)^{k-1}\sum_{j=1}^nx_j\binom{n-j}{k-1}\\ &=\sum_{j=1}^nx_j\sum_{k=1}^n(-1)^{k-1}\binom{n-j}{k-1}\\ &=\sum_{j=1}^nx_j\,[j=n]\\[9pt] &=x_n \end{align} $$ Compare this to this proof of the Inclusion-Exclusion Principle.