Avraham A. Melkman

e-mail: melkman@cs.bgu.ac.il

Solomon Eyal Shimony

e-mail: shimony@cs.bgu.ac.il

Ben-Gurion University - Math. and Comp. Sci. Dept.

P. O. Box 653

84105 Be'er Sheva, Israel

FAX : +972-7-472909

Given a sequence of n sets, it was shown by Kahn, Linial and Samorodnitsky that if it is known that u, the size of the union of all the sets, is less than 2^(n-1), then it can be determined uniquely from just the sizes of the intersections (but without knowing the size of the intersection of all n sets). Since their proof was existential they posed the question of finding an adaptive procedure for determining $u$. Here we present such an algorithm, and discuss the proof of some exact bounds on the intersection sizes when the above conditions do not hold.

Inclusion-exclusion, DNF model counting.

Jeff Kahn, Nathan Linial, and Alex Samorodnitsky. Inclusion-exclusion: Exact and approximate. Combinatorica, (in print).

Nathan Linial and Noam Nisan. Approximate inclusion-exclusion. Combinatorica, 10:349-365, 1990.

Short version of paper - to appear in Discrete Applied Mathematics.Long version of this paper is available in (PostScript) format.

shimony@cs.bgu.ac.il / Last update: 20 July 1996