Simplifying inclusion-exclusion formulas

Abstract

Let $\mathcal{F}=\{F_1,F_2,\dots ,F_n\}$ be a family of $n$ sets on a ground set $S$, such as a family of balls in ${\mathbb{R}}^d$. For every finite measure $\mu$ on $S$, such that the sets of $\mathcal{F}$ are measurable, the classical inclusion-exclusion formula asserts that $\mu (F_1\cup F_2\cup \cdots \cup F_n)={\sum }_{I:\varnothing \ne I\subseteq [n]}(-1{)}^{|I|+1}\mu ({\bigcap }_{i\in I}{F}_i)$; that is, the measure of the union is expressed using measures of various intersections. The number of terms in this formula is exponential in $n$, and a significant amount of research, originating in applied areas, has been devoted to constructing simpler formulas for particular families $\mathcal{F}$. We provide an upper bound valid for an arbitrary $\mathcal{F}$: we show that every system $\mathcal{F}$ of $n$ sets with $m$ nonempty fields in the Venn diagram admits an inclusion-exclusion formula with $m^{O({\log }^{2}n)}$ terms and with $\pm 1$ coefficients, and that such a formula can be computed in $m^{O({\log }^{2}n)}$ expected time. For every $\epsilon >0$ we also construct systems with Venn diagram of size $m$ for which every valid inclusion-exclusion formula has the sum of absolute values of the coefficients at least $\Omega (m^{2-\epsilon })$.

17 pages, 3 figures/tables; improved lower bound in v2