If $E$ denotes $n$ sets of size $k$, what is the minimum possible number of subsets of sets in $E$ of size $d$, $d<k$?

26 Views Asked by At

Let $X$ be a set of size $N$ and $E$ be a family of subsets of $X$ of size $k \in \mathbb{N}$, i.e. $E\subseteq [X]^k$, with $k\geq 2$.

Fix $1\leq d <k$. Let $U$ denote the family of subsets of $X$ of size $d$ that are also subsets of some set in $E$. What is the minimum possible size of $U$?

For example, if $E=[X]^k$ then $|E|= \binom{N}{k}$ and $|U|= \binom{N}{d}$, so $$ |U|=|E|\frac{(N-k)!}{(N-d)!}\frac{k!}{d!}. $$ Is this optimal?

Note moreover that, since $|E|<N^k$ and, for $N$ large enough (or $|E|$ large enough), $U > N^{d-1}$, then for $E$ large enough, we have that $$ |U| > |E|^{\frac{d-1}{k}}. $$
Does this inequality hold for every possible $E$?