Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I would like to prove the following statement:

Let $E$ be a set with $n$ elements, and let $k$ be an integer such that $1\leq k<n-k$. Let $r\leq\binom{n}{k}$ and $\mathcal{A}$ be a set of $r$ subsets of $E$ with $k$ elements. Then the number of subsets of $E$ with $n-k$ elements which contain (as a subset) at least one element of $\mathcal{A}$ is $\geq r$.

At the moment, I have no idea. Straightforward induction doesn't seem to be the right way here. I'd be glad for any kind of help.

share|cite|improve this question
The subsets of $E$ do not contain elements of $\mathcal{A}$ (which are sets in their own right), but may have them as subsets. – Ross Millikan Apr 23 '11 at 15:58
up vote 3 down vote accepted

There are exactly $w=\binom{n-k}{n-2k}=\binom{n-k}{k}$ ways to extend a $k$ set to a $n-k$-set. But there also exactly this number of $k$-sets contained in a $n-k$-set.

Therefore, the sets in $A$ give rise to $r\cdot w$ admissible $(n-k)$-sets where each set has been counted at most $w$ times, so there are at least $r$ of them.

(Note that the $k$-sets and $(n-k)$-sets together with the inclusion property form a bipartite $w$-regular graph which is a standard exercice for the condition of the marriage theorem.)

share|cite|improve this answer
Thank you very much! – Stefan Apr 23 '11 at 16:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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