Simplifying Inclusion–Exclusion Formulas

Abstract

Let $\mathcal{F}$ = { F 1 , F 2 ,. . ., F n } be a family of n sets on a ground set S , such as a family of balls in ℝ d . For every finite measure μ 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:\emptyset\ne I\subseteq[n]} (-1)^{|I|+1}\mu\biggl(\bigcap_{i\in I} F_i\biggr),\]$ 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 non-empty fields in the Venn diagram admits an inclusion–exclusion formula with m O (log 2 n ) terms and with ±1 coefficients, and that such a formula can be computed in m O (log 2 n ) expected time. For every ϵ > 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 Ω( m 2−ϵ ).

Locations

• reroDoc Digital Library - View - PDF
• arXiv (Cornell University) - View - PDF
• Repository for Publications and Research Data (ETH Zurich) - View - PDF
• HAL (Le Centre pour la Communication Scientifique Directe) - View
• Combinatorics Probability Computing - View