Set Theory · Introduction

Lesson 11

Nikolai Chukhin · Alexander S. Kulikov

The inclusion-exclusion formula is a widely known identity. It allows expressing the size of the union of sets in terms of the sizes of their intersections:

\[\begin{align*}|A_{1} \cup A_{2}|&= |A_{1}|+|A_{2}|-|A_{1} \cap A_{2}|\\ |A_{1} \cup A_{2} \cup A_{3}|&= |A_{1}|+|A_{2}|+|A_{3}| -|A_{1} \cap A_{2}|-|A_{1} \cap A_{3}|-|A_{2} \cap A_{3}| +|A_{1} \cap A_{2} \cap A_{3}|\end{align*}\]

Theorem (inclusion-exclusion formula). Let \(U\) be a finite set and \(A_{1}, \dotsc, A_{n} \subseteq U\). \[\begin{align*}\left| \bigcup_{i \in [n]}A_{i}\right|&=\sum\limits_{I \subseteq [n]}(-1)^{|I|+1}\left| \bigcap\limits_{i \in I}A_{i}\right|,\\ \left| \bigcap_{i \in [n]}A_{i}\right|&= \sum\limits_{I \subseteq [n]}(-1)^{|I|}\cdot \left| \bigcap\limits_{i \in I}(U \setminus A_{i})\right| \ .\end{align*}\] We assume that \(\bigcap_{i \in \varnothing}A_{i} = \varnothing\), but \(\bigcap_{i \in \varnothing}(U \setminus A_{i})=U\).

Proof. We will prove each of the two formulas in different ways. To prove the first formula, consider the characteristic function of the set \(A \colon U \to \{0,1\}\), defined by the relation \(\chi_{A}(u)=[u \in A]\). It is easy to verify that it has the following properties:

  • \(|A|=\sum_{u \in U}\chi_{A}(u)\);

  • \(\chi_{\overline A}=1 \oplus \chi_{A} = 1-\chi_{A}\);

  • \(\chi_{A \cap B}=\chi_{A} \land \chi_{B}=\chi_{A} \cdot \chi_{B}\);

  • \(\chi_{A \cup B}=\chi_{A} \lor \chi_{B}=1-(1-\chi_{A}) \cdot (1-\chi_{B})\).

Then the characteristic function of the union of sets is \[1-(1-\chi_{A_1})(1-\chi_{A_2})\dotsb(1-\chi_{A_n}) \ .\] In this formula, we can expand the brackets, then replace each term of the form \(\prod_{i \in I}\chi_{A_i}\) with \(\chi_{\cap_{i \in I}A_i}\), and finally, add summation over all \(u \in U\) (then each such function will be replaced by the size of the corresponding set) — and we will get the desired formula! (The unity will cancel out: it corresponds to \(I=\varnothing\).)

To prove the second formula, consider an element \(u\) and assume that it belongs to the sets \(A_{1}, \dotsc, A_{k}\) and only to them (the sets can always be renumbered in this way). Then \(u \in \bigcap_{i \in I}(U \setminus A_{i})\) if and only if \(I \cap [k] = \varnothing\). The contribution of this element to the right-hand side is \[\sum_{I \subseteq [n] \setminus [k]}(-1)^{|I|}=\sum_{i=0}^{n-k}\binom{n-k}{i}\cdot (-1)^{i}=(1-1)^{n-k}=[n=k] \ .\]◼

For the curious 🤓
There are many combinatorial problems solved using the inclusion-exclusion formula. It turns out that this formula also has unexpected applications in the field of algorithms for NP-hard problems!

The Hamiltonian cycle problem is algorithmically hard: we still don't know polynomial-time algorithms for it. Using dynamic programming, it can be solved in time \(O^{*}(2^{n})\). The corresponding algorithm has exponential time complexity and uses exponential memory. Below, we will use the inclusion-exclusion formula to build an algorithm with a time complexity of \(O^{*}(2^{n})\) and polynomial memory (\(O^{*}(\cdot)\) hides factors that polynomially depend on the input size).

Theorem. It is possible to check whether a given graph contains a Hamiltonian cycle in time \(O^{*}(2^{n})\) and polynomial memory.

Proof. Let \(A_{j}\) be the number of walks consisting of \(n\) edges of the form \[1 \to \dotsb \to j \to \dotsb \to 1\] (i.e., starting and ending at vertex 1 and passing through vertex \(j\)). The word “walk” here means that both vertices and edges may repeat. Then, \(|\cap A_{i}|\) is exactly the number of Hamiltonian cycles. To use the inclusion-exclusion formula, it is sufficient to find how to compute in polynomial time the number \(|\cap_{i \in I}(U \setminus A_{i})|\), where \(I \subseteq V\). It is equal to the number of closed walks of length \(n\) from the first vertex in the graph induced by the set \(V\setminus I\). And this can be computed as \(B^{n}[1][1]\), where \(B\) is the adjacency matrix of this graph (it can also be computed using dynamic programming).◼