Suppose I have n finite sets A1 through An contained in some fixed set S, and I am given non-negative integers N and N1 through Nn such that each Ai has cardinality N, and each k-tuple intersection has cardinality less than or equal to Nk.


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



Bound on cardinality of a union
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.


