There are a couple of noteworthy facts related to the complement sparsity lemma we proved last time. First, the l-parameter of the extension can be generalized into any multiple of m: $$ \kappa \left[ {X \choose im} – Ext({\mathcal F}, im) \right] \ge i~ \kappa \left[ {X \choose m} – {\mathcal F} \right]. \quad \textrm{for}~ i \in \left[1, \frac{n}{m} \right]. $$ This is proven by induction on i with essentially the same arguments as our last proof, also as discussed on p. 13-14 of Paper 4. For a claim in a paper like Paper 3 to use for another proof, I usually just present the case i=2 for clear exposition.
It is clearly true for i=1 as the base case. For the induction step assuming it for i, we think of pairs (V, Y) such that \( Y \in Ext [{\mathcal F}, (i+1)m] \) and \( V \in Ext ({\mathcal F}, im) \cap {Y \choose i m} \). There are $$ |Ext( {\mathcal F}, im)| ~{n-i m \choose m}={n \choose im} v_i {n-i m \choose (i+1)m – im} = v_i {n \choose (i+1)m}{(i+1)m \choose im} $$ such pairs by the identity \( {n \choose m}{n – m \choose l-m}={n \choose l}{l \choose m}\), where \( v_i = e^{-\kappa [ Ext( {\mathcal F}, im ) ]} \).
To count \( (V’, Y) \) such that \( V’ \in {X \choose im} – Ext ({\mathcal F}, im) \), fix each \( V’ \) and place all \( U \in {\mathcal F} \) the same way as the figure last time. (Replace U’ there by V’. There may be \( U \) completely contained in the \( V’ \) unlike the last time. But this doesn’t change the argument.) Then there is an \( {\mathcal F}_j \) such that \( \kappa ({\mathcal F}_j ) \le \kappa ({\mathcal F}) \), so $$ |Ext[{\mathcal F}, (i+1)m][V’]|\ge {n -im \choose m} e^{-\kappa({\mathcal F})} = v_1 {n -im \choose m}, $$ producing the same number of \( (V’, Y) \). Their total for all \( V’ \) is \( v_1 (1- v_i ) {n \choose (i+1) m}{(i+1)m \choose im} \) or more seen the same way.
So, the total number of \( (V, Y) \) and \( (V’, Y) \) such that \( Y \in Ext[{\mathcal F}, (i+1)m] \) is at least $$ [v_i + v_1 (1- v_i ) ] {n \choose (i+1) m}{(i+1)m \choose im}.$$ Put \( z = 1 – v_1 \) to view this in terms of the complement sparsity of \( {\mathcal F} \) that is \( – \ln z \). The complement sparsity of \( Ext ({\mathcal F}, im ) \) equals \( – \ln (1 – v_i ) \) because \( \left| {X \choose im} – Ext ({\mathcal F}, im ) \right| = {n \choose im} e^{\ln (1-v_i) } \). It satisfies $$ – \ln (1 – v_i) \ge – i \ln z, \qquad \Rightarrow \qquad v_i \ge 1 – z^i, $$ by induction hypothesis.
Now the above lower bound is \( {n \choose (i+1) m}{(i+1)m \choose im} \) times $$ v_i + v_1 (1- v_i ) = v_1 + (1-v_1) v_i \ge 1-z + z (1-z^i) = 1 – z^{i+1}. $$ In other words, by the same last step as last time, the complement sparsity of \( Ext [{\mathcal F}, (i+1)m ] \) is at least i+1 times \( – \ln z \) that is the complement sparsity of \( {\mathcal F} \). This completes the induction step proving the above generalized bound.
Our second remark is that the obtained bound is approximately the best we could get. Let’s see it next time.
Links for mobile devices