Number of sets containing some given sets of fixed cardinality

Question

Assume to have $L$ sets $T_1,\ldots,T_L \subseteq \{1,\ldots,n\}$ of cardinality $k\leq n$. Consider an integer $m$ such that $k\leq m \leq n$ and define $$ \mathcal{S} := \{T'\subseteq\{1,\ldots,n\} : T_j \subseteq T' \text{ for some index } j \text{ and } |T'| = m\}. $$ How to find a good lower bound to $|\mathcal{S}|$? Ideally, I would like to show that $$ |\mathcal{S}| \geq \frac{{n \choose m}}{{n \choose k}} L. $$ Maybe this is a standard problem in combinatorics, but I don't know what keywords to look for. Any literature reference would be highly appreciated.

Answer 1

Let $I = \{(T_j,T') : 1 \leq j \leq L, T_j \subseteq T', |T'|=m\}$. Projection on the first factor is $\binom{n-k}{m-k}$-to-$1$, so $|I|=\binom{n-k}{m-k}L$. Projection on the second factor is at most $\binom{m}{k}$-to-$1$, so $|I| \leq \binom{m}{k}|S|$. This shows $$ |S| \geq \frac{\binom{n-k}{m-k}}{\binom{m}{k}}L . $$ Edit: And note that $$ \frac{\binom{n-k}{m-k}}{\binom{m}{k}} = \frac{\binom{n}{m}}{\binom{n}{k}} $$ which proves the bound you were looking for.