The complement sparsity lemma and its generalization proven last time are approximately the best we could get. It’s because we can create a situation where we can’t much improve its performance.
Let \( X = \{ 1, 2, \ldots, n\},~~ X_k = \{ 1, 2, …, k \},~ \) and \( {\mathcal F} \subset {X \choose m} \) be the family of m-sets each including at least one element of \( X_k \). Regarding \( X_k \) as the family of 1-sets, \( {\mathcal F} \) meets $$ {\mathcal F} = Ext (X_k,~m), \qquad \textrm{and} \qquad |{\mathcal F}| = {n \choose m} – {n-k \choose m}, $$ because the complement of \( {\mathcal F} \) is the family of m-sets including no elements of \( X_k \), so \( \left| {X \choose m} – {\mathcal F} \right| = {n-k \choose m} \).
The complement cardinality can be estimated accurately with Lemma 2.4 on p. 31 of Paper 4. It says $$ (1) \qquad {n – k \choose m} \simeq {n \choose m} \exp \left( – \frac{mk}{n} \right), $$ when \( m+ k \ll n \), i.e., both m and k are much smaller than n. It holds since $$ \frac{{n-k \choose m}}{{n \choose m}} = \frac{(n-k)(n-k-1)\cdots (n-k-m+1)}{n(n-1) \cdots (n-m+1)} $$ $$ = \frac{n-k}{n} \cdot \frac{n-1 -k}{n-1} \cdots \frac{n-m+1 – k}{n-m+1} = \prod_{i=0}^{m-1} \left( 1 – \frac{k}{n-i} \right) $$ $$ \simeq \left( 1 – \frac{k}{n} \right)^m = \left[ \left( 1 – \frac{k}{n} \right)^{n/k} \right]^{mk/n} \simeq \exp \left( – \frac{mk}{n} \right). $$ The approximations are accurate as long as \( m+k \ll n \): the first \( \simeq \) is good because \( n-i \simeq n \) due to \( i < m \ll n\), and the second one is because of \( n \gg k \) so \( n’ = n/k \) is big considered in \( \lim_{n’ \rightarrow \infty} (1-1/n’)^{n’} = e^{-1} \). (More precisely, the approximation quality can be shown with the Taylor series of \( \ln (1+x) \) as Lemma 2.4 does. )
If n and m+k are of the same order such as \( m+k = \epsilon n \) for a constant \( \epsilon \in (0, 1) \), the exponent in (1) becomes \( – c \frac{nk}{n} \) where c>0 is a constant depending on \( \epsilon \). It’d still make a good approximation for many applications.
In summary, we took the m-extension of \( X_k \) into \( {\mathcal F} \), and its complement sparsity is approximately \( mk/n \) by (1). Further take the l-extension of \( {\mathcal F} \), and its complement sparsity is approximately \( l k / n \), since \( Ext ({\mathcal F}, l ) = Ext (X_k, l ) \). Recalling the generalized bound of the complement sparsity lemma, if we extend m-sets into l-sets, we get its complement sparsity at least \( l/m \) fold. And that lower bound accurately matches with the upper bound here because \( \frac{lk}{n} \Big/ \frac{mk}{n} = \frac{l}{m}. \)
More specifically, let \( k= n^{3/4},~\) \( m = \sqrt n,~ \) and \( l = n^{3/4},~ \) and we have $$ \kappa \left[ {X \choose m} – {\mathcal F} \right] \simeq \frac{mk}{n} = n^{1/4}, \quad \textrm{and} \quad \kappa \left[ {X \choose l} – Ext ({\mathcal F}, l)\right] \simeq \frac{lk}{n} = \sqrt n. $$ The lemma says the latter is at least \( l/m = \sqrt[4] n \) times the former, and we’re seeing in this example we can’t do much better than that.
It doesn’t change a lot even if we take a larger l such as \( l = \epsilon n \): the obtained \( \kappa \left[ {X \choose l} – Ext({\mathcal F}, l) \right] \) is \( c l / m \) as seen above, being just a constant fold improvement over \( l / m \).
Links for mobile devices