Number of subsets with $n-k$ elements containing at least one of a given set of subsets with $k$ elements

Question

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.

Answer 1

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