Martin Tancer: Simplifying inclusion-exclusion formulas

Given a family {F_1, ..., F_n} of sets and finite measure on the union, the classical inclusion-exclusion principle allows us to compute the measure of the union of the sets in the family from measures of intersections. A disadvantage of this formula is that it contains number of terms exponential in n. A significant amount of research was devoted to simplifying this formula for particular families.

  The task of the talk is to present simplifications valid for all families where the formula has +/- 1 coefficients, and the size of simplified formula depends (quasi-polynomially) on n and on the number of nonempty regions in the Venn diagram of the family. One of the steps of the simplification is a construction of suitable simplicial complexes, called abstract tubes, for the given family.
We also present lower bounds of order n^{3/2}.

(joint work with Xavier Goaoc, Jiri Matousek, Pavel Patak and Zuzana Safernova)