Abstrakt
Let 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 R d. For every finite measure μ on S, such that the sets of F are measurable, the classical inclusion-exclusion formula asserts that μ (F 1 ∪ F 2 ∪ …∪ F n) = ∑I:ø≠⊆[n] (−1)¦I¦+1μ(∩i ∈IF 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 an 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 (log2 n) terms and with ±1 coefficients, and that such a formula can be computed in m O (log2 n) expected time.