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}).
Type de document :
Communication dans un congrès
European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy. 2013
Liste complète des métadonnées

https://hal.inria.fr/hal-00764182
Contributeur : Xavier Goaoc <>
Soumis le : mercredi 12 décembre 2012 - 15:12:50
Dernière modification le : jeudi 22 septembre 2016 - 14:31:10

Identifiants

  • 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. 2013. 〈hal-00764182〉

Partager

Métriques

Consultations de la notice

281