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.

  • $\begingroup$ The subsets of $E$ do not contain elements of $\mathcal{A}$ (which are sets in their own right), but may have them as subsets. $\endgroup$ – Ross Millikan Apr 23 '11 at 15:58

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


Your Answer

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

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