Simplifying Inclusion–Exclusion Formulas

Abstract: Let

m a t h c a l F = F_{1}, F_{2}, l d o t s, F_{n}

be a family of

n

sets on a ground set

S

, such as a family of balls in

m a t h b b R^{d}

. For every finite measure

m u

on

S

, such that the sets of

m a t h c a l F

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

m a t h c a l F

. We provide an upper bound valid for an arbitrary

m a t h c a l F

: we show that every system

m a t h c a l F

of

n

sets with

m

nonempty fields in the Venn diagram admits an inclusion-exclusion formula with

m^{O (l o g^{2} n)}

terms and with

p m 1

coefficients, and that such a formula can be computed in

m^{O (l o g^{2} n)}

expected time. For every

v a r e p s i l o n > 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

O m e g a (m^{2 - v a r e p s i l o n})

.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Simplifying Inclusion–Exclusion Formulas