Covering small subsets with complements of large subsets

Question

Consider three integers $n,m,k$ such that $n > m$ and $n-m > k$ (for simplicity, say $m = n/4$ and $k \ll n$). I am interested in finding the minimum number $L$ of subsets $I_1, I_2, \dots I_L \subset \{1,\dots,n\}$ of size $m$ such that each $J \subset \{1,\dots,n\}$ of size $k$ is disjoint from at least one $I_j$. In other words, $\cup_{1\leq j \leq L} \binom{[n]\setminus I_j}{k}$ must be equal to $\binom{[n]}{k}$. What upper bound can we show on $L$?

Answer 1

The optimal number of sets is around $L \approx (4/3)^k$ (assuming $m=n/4$ and $k \ll n$):

Upper bound:

Fix any k-sized set $S$. Randomly sample $L$ different subsets. The probability a sampled set $I$ is disjoint from $S$ is $\binom{n-k}{n/4}/\binom{n}{n/4} \approx (3/4)^k$. The probability that none of the sets sampled are disjoint from $S$ is then at most $(1 - (3/4)^k)^L$. Setting $L = (4/3)^k \cdot \ln \binom{n}{k} \approx k \cdot \ln n \cdot (4/3)^k$, this is less than $1/\binom{n}{k}$.

Using a union bound over all $k$-sized subsets, there is a greater than zero probability that the sampled sets are as you wished. Hence there is a fixing of the sets so that for every $k$-sized subset, at least one of the sets are disjoint from it. So $L \leq k \cdot \ln n \cdot (4/3)^k$.

Lower bound:

This probabilistic argument is also fairly tight. You can't do it with $L < (4/3)^k$. That's because we can just choose the $i \in [n]$ that appears in the most number of the $I_j$s. This $i$ must appear in at least $1/4$ of the $I_j$s. Taking this element as the singleton set $S$, already these $1/4$ fraction of sets are not disjoint from it, so at most 3/4 of the sets can be disjoint from the singleton. We can repeat on the remaining sets to get an $S$ of size $k$ so that at most $(3/4)^k$ fraction of the sets are disjoint from it. If $L < (4/3)^k$, that means none of the sets are disjoint from it.