Continued from the last time, we see this lemma in this and the next couple of posts.
Complement Sparsity Lemma: \( \kappa \left[ {X \choose 2m} – Ext({\mathcal F}, 2m) \right] \ge 2 \kappa \left[ {X \choose m} – {\mathcal F} \right]. \)
Here \( {X \choose m} – {\mathcal F} \) is the complement of \({\mathcal F} \), the family of m-sets not included in \( {\mathcal F} \). This is Lemma 2.5 on p. 8 of Paper 3, with the same arguments given in Section 3.2 of Paper 4, also used by the current version of Paper 2. It says that the sparsity of the complement doubles when you take the 2m-extension of \( {\mathcal F}\).
Given an \( {\mathcal F} \subset {X \choose m} \) for the EGT satisfying some \( \Gamma\)-condition, suppose we achieve \( |Ext ({\mathcal F},~l_0 )| > \frac{2}{3} {n \choose l_0} \) for some integer \(l_0 \) that’s a bit larger than \( m^2 \). This is very doable with Corollary 2.6 on p. 9 of Paper 3, whose details we’ll see soon. With e=2.71…., $$ |Ext ({\mathcal F},~l_0 )| > ( 1 – e^{-1} ) {n \choose l_0}, \quad \Rightarrow \quad \kappa \left[ {X \choose l_0 } – Ext({\mathcal F}, l_0 ) \right] > 1. $$ In other words, the complement sparsity of \( {\mathcal F}_0 = Ext({\mathcal F},~l_0 ) \) is greater than 1.
Then take the \( 2 l_0 \)-extesion of \( {\mathcal F}_0 \), whose complement sparsity is greater than 2 by the lemma. Put the extended family in \( {\mathcal F}_1 \), and take its \( 4 l_0 \)-extesion \( {\mathcal F}_2 \) so its complement sparsity is greater than 4. We can continue this for \( 8 l_0 \)-extension \( {\mathcal F}_3 \), \( 16 l_0 \)-extension \( {\mathcal F}_4 \) and more as long as the l-parameter is less than n=|X|. Consequently, the complement sparsity of \( {\mathcal F}_i \) is greater than \( 2^i \) meaning that $$ |{\mathcal F}_i| > {n \choose 2^i l_0} \left(1 – e^{-2^i} \right) \quad \textrm{where}\quad {\mathcal F}_i = Ext ({\mathcal F},~2^i l_0 ). $$ Here \( {\mathcal F}_i \) has been obtained by taking 2l-extesions i times repeatedly, so it’s nothing but the \( 2^i l_0 \)-extension of \( {\mathcal F} \).
Now recalling the \( \lambda \) parameter of EGT in the 2/23 post, choose \( i = \log_2 \lambda \) setting \( l = 2^i l_0 \) that’s a bit lager than \( \lambda m^2 \). This achieves $$ |Ext ( {\mathcal F},~l)| > {n \choose l} \left( 1 – e^{-\lambda} \right), $$ so an empty set is an \( (l, \lambda) \)-extension generator of \( {\mathcal F} \).
For a general \( {\mathcal F} \) and \( \lambda \) such that \( 1 < \lambda < \epsilon l / m^2 \) for a given small enough constant \( \epsilon>0 \), we can set \( l_0 = l \sqrt \epsilon / \lambda\) and \( b = 4 mn \sqrt[4] \epsilon / l \) just as on page 9 of Paper 3. Find a maximal set S such that \( | {\mathcal F}[S]| \ge b^{-|S|} | {\mathcal F}| \), and you can see \( |S| \le \kappa ({\mathcal F}) \big/ \frac{\epsilon l}{\lambda m^2} \) following the inequalities in the middle of page 8.
Because S is maximal, another \( S’ \ne S \) including \( S \) can’t make \( | {\mathcal F}[S’]| \ge b^{-|S’|} | {\mathcal F}| \), that is, \( {\mathcal F}[S] \) satisfies the \( \Gamma(b) \)-condition in X-S. So we can do the above for \( {\mathcal F}[S] \) in X-S to see S is an \( (l, \lambda) \)-extension generator of \({\mathcal F} \).
This is the outline of the proof of EGT from the lemma and Corollary 2.6. Let’s prove the lemma next time.
Links for mobile devices