Bound on cardinality of a union

Question

Suppose I have n finite sets A₁ through A_n contained in some fixed set S, and I am given non-negative integers N and N₁ through N_n such that each A_i has cardinality N, and each k-tuple intersection has cardinality less than or equal to N_k.

Can I use this to construct a good lower bound on the cardinality of the union of the A_i?

Answer 1

I don't know your reason for asking this question, so it's unlikely that what I'm about to write will be helpful. Nevertheless, there's an easy method I like a lot for deducing a lower bound just from the knowledge that N_2 is small. It may be contained in what has been said above -- I haven't checked.

The idea is to think of each set A_ i as a 01-valued function on a set of size M. We then look at the ell_ 2 norm of sum_i A_i. The square of the ell_ 2 norm is sum_ {i,j}|A_ i cap A_ j|, which by assumption is at most nN + n(n-1)N_ 2. But we also have a lower bound: the ell_ 1 norm of the sum is nN, from which it follows that the square of the ell_ 2 norm is at least (nN)^2/M.

Putting these two bits of information together gives a lower bound for M of nN/(1+(n-1)N_ 2/N). So, for example, if N_ 2 = cN for some smallish positive constant c, then the lower bound is roughly N/c.

Answer 2

(edit: As Reid Barton pointed out I'm assuming here that you have some sort of lower bound on the N_k as well as an upper bound...if this is not the case then including more terms won't help at all)

To generalize Hugh Thomas' answer, one option might be to take a look at what the Bonferonni Inequalities give you. Essentially you can stop inclusion-exclusion after any subtraction and you'll always be left with a lower bound.

So if you don't have enough of the N_k to run inclusion-exclusion all the way through, or if it makes the computation intractable, see what the best lower bound you can get from what you have is.

Answer 3

A better solution than my previous one is

max_{1\leq i \leq n} iN - {i \choose 2}N_2

(That is to say, we can simply consider only i of the sets instead of all n of them, and then apply my previous argument to obtain a lower bound on the size of the union of those i sets, which is also a lower bound on the size of the total union.)

In fact, one can figure out the value of i which maximizes this bound: it will be the largest i for which N - (i-1)N_2 is positive (since this is the difference between the bound obtained using i and that obtained using i-1). This is i = \lfloor N/N_2 \rfloor +1.

So, taking that value for i, the best solution I can see is

nN - {n\choose 2} N_2 if n< i and otherwise iN - {i \choose 2} N_2.

This is, at least, non-negative. In the latter case, it's on the order of N^2/(2N_2).

**

Of course, I'm still not using all the information. I don't see how to get anything further out of inclusion-exclusion when all we have are upper bounds on the sizes of the triple and higher intersections. I encourage anyone who thinks there is an argument in there to post it.

(Edited to correct my arithmetic for the order of the bound in the i <= n case.)

Answer 4

There is the obvious lower bound of nN - {n \choose 2}N_2.

(I'm taking N_2 to be the bound on the size of an intersection of 2 sets; I'm not sure if that's what you meant.)

I don't think it's possible to do better in general, because the triple and larger intersections might all be zero, in which case the above bound is achieved.

Of course, one might be able to say more in a more special situation -- did you have something more specific in mind?

Answer 5

Use the inclusion-exclusion principle.