Simplifying Inclusion–Exclusion Formulas

Abstract : Let = {F1, F2,. . ., Fn} 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 are measurable, the classical inclusion–exclusion formula asserts that 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 . We provide an upper bound valid for an arbitrary : we show that every system of n sets with m non-empty fields in the Venn diagram admits an inclusion–exclusion formula with m^O(log2n) terms and with ±1 coefficients, and that such a formula can be computed in m^O(log2n) 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−ϵ}).
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.inria.fr/hal-01578188
Contributeur : Xavier Goaoc <>
Soumis le : lundi 28 août 2017 - 17:15:16
Dernière modification le : jeudi 11 janvier 2018 - 06:20:23

Identifiants

Collections

Citation

Xavier Goaoc, JiŘÍ MatouŠek, Pavel Paták, Zuzana Safernová, Martin Tancer. Simplifying Inclusion–Exclusion Formulas. Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2015, 24 (02), pp.438 - 456. 〈https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/simplifying-inclusionexclusion-formulas/BB9463B894400E46ED8D62881D2F017F〉. 〈10.1017/S096354831400042X〉. 〈hal-01578188〉

Partager

Métriques

Consultations de la notice

71