This question specifically refers to a previous discussion from this website, namely, minimizing the intersection of three sets.

As per that discussion, let us consider a finite set N, and a finite collection of subsets A,B,C.... My aim is under suitable restrictions on their size, to determine a non trivial lower bound on the intersection of the above family of subsets.

The Principle of Inclusion Exclusion is used (I add it here for reference), where the union of the subsets is bounded by the number of elements in N; I believe that one has to be careful about the sums of the sizes of the subsets to justify this. I can see how the formula for 2 subsets would be derived, as per the discussion, yet I do not see how subsequent uses of the principle thereof are justified for the case of 3 subsets or more. I am struggling to generalize the result. Maybe induction could be yield some, yet all my attempts have failed. Maybe an application of de Morgan's law to convert the inclusion exclusion formula to this one from another post using unions. The binomial coefficients, if isolated, would yield the desired result (as per the post above by Boyku).

Any help would be appreciated.

The motivation comes from the desire to find a rigorous solution and a generalization to the following question from a UK maths competition (senior kangaroo from 2015) (Number 14).

Thanks in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.