Simplifying inclusion-exclusion formulas

Abstract : Let F = {F_1, F_2,..., F_n} be a family of n sets on a ground set X, such as a family of balls in R^d. For every finite measure \mu on X, such that the sets of F are measurable, the classical inclusion-exclusion formula asserts that \mu(F_1 \cup F_2 \cup \bullet \bullet \bullet \cup F_n) = \sum_{I:{\O} \neq I\subseteq[n]} (-1)^{|I|+1} \mu(\cap_{i\inI} 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 F. We provide the apparently first upper bound valid for an arbitrary F: we show that every system F of n sets with m nonempty fields in the Venn diagram admits an inclusion- exclusion formula with m^O((log n)^2) terms and with \pm1 coefficients, and that such a formula can be computed in m^O((log n)^2) expected time. We also construct systems of n sets on n points for which every valid inclusion-exclusion formula has the sum of absolute values of the coefficients at least \Omega(n^{3/2}).
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00764182
Contributor : Xavier Goaoc <>
Submitted on : Wednesday, December 12, 2012 - 3:12:50 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM

Links full text

Identifiers

  • HAL Id : hal-00764182, version 1
  • ARXIV : 1207.2591

Collections

Citation

Xavier Goaoc, Jiří Matoušek, Pavel Paták, Zuzana Safernová, Martin Tancer. Simplifying inclusion-exclusion formulas. European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy. ⟨hal-00764182⟩

Share

Metrics

Record views

372