6
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Have you tried wrangling with inclusion-exclusion yet? That gives you a bound, although you have to ignore the terms that are the wrong sign. $\endgroup$ Oct 28, 2009 at 17:17
  • $\begingroup$ A straightforward application of inclusion-exclusion, ignoring the terms of the wrong sign, gives a lower bound. But it will generally be far from optimal. $\endgroup$ Oct 28, 2009 at 18:46

5 Answers 5

9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, this gives a much better estimate; maybe this is all one can reasonably say. As for motivation, an answer to this question gives an upper bound for Ramsey numbers, see the tag. (In some cases it is very close, though not better, than the best known upper bound.) $\endgroup$ Oct 29, 2009 at 20:49
8
$\begingroup$

(edit: As Reid Barton pointed out I'm assuming here that you have some sort of lower bound on the Nk 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 Nk 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.

$\endgroup$
1
  • 2
    $\begingroup$ Hmm, but we only have upper bounds on the sizes of the k-tuple intersections, so we don't get to count anything for the positive terms; and including negative terms beyond the first will only make our bound worse. $\endgroup$ Oct 29, 2009 at 1:00
5
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ This bound might be negative. More generally, if the double intersections all have size N_2 that might force at least some of the triple intersections to be nonempty. $\endgroup$ Oct 28, 2009 at 18:49
0
$\begingroup$

Use the inclusion-exclusion principle.

$\endgroup$
1
  • $\begingroup$ Oops, I hadn't noticed Qiaochu Yuan's comment on the question before answering. $\endgroup$ Oct 28, 2009 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.