We’ve seen some facts about sparsity in the last five posts mainly discussing the complement sparsity lemma. As said in the 6/29 post, the lemma together with Corollary 2.6 on p.9 of Paper 3 proves the EGT. The corollary is the unweighted simplification of Theorem 2.3 on p. 6 of Paper 3. So let’s prove the corollary first, then generalize it into Theorem 2.3. This will prove the EGT and its unwritten weighted variant.
I’ve uploaded my write-up that proves the EGT with extra intuitive explanations. Please take a look at the new paper S3 on the left. This version is something I used for a long time so it’s sturdy. The argument in Section 3 is the same as Paper 3 including Corollary 3.2 claiming the same. Let me rephrase what it says:
Corollary 3.2 of Paper S3: let \( \gamma>0 \) be sufficiently large and \( l \in ( \gamma m^2, n) \). Also let \({\mathcal F} \subset {X \choose m} \) satisfy the \( \Gamma(b) \)-condition where \( b= \frac{5 \gamma mn}{l} \). There are \( {n \choose l} \left( 1 – \frac{2}{\sqrt[3] \gamma } \right) \) sets \( Y \in {X \choose l} \) such that \( \left| {\mathcal F} \cap {Y \choose m} \right| \) each equal \( {l \choose m} |{\mathcal F}| \Big/ {n \choose m} \) up to a factor between \( 1 \pm \frac{1}{ \sqrt[3] \gamma} \).
So if \( {\mathcal F} \) satisfies the \( \Gamma \)-condition with b sufficiently larger than \( mn / l \), almost all \( l \)-sets \(Y \) include about \( {l \choose m} |{\mathcal F}| \Big/ {n \choose m} \) sets \( U \in {\mathcal F} \). This is responsible for the first part of the EGT proof before the complement sparsity lemma: in the 6/29 post, we used it to show \( Ext ( {\mathcal F}, l_0 ) \) has complement sparsity greater than 1, so \( \kappa \left[ {X \choose l} – Ext ( {\mathcal F}, l ) \right] > \frac{l}{l_0} \) to finalize the EGT, by the generalized complement sparsity lemma given in the 7/13 post. That \( l_0 \) is \( l \simeq \gamma m^2 \) here. We want to show U are evenly distributed over most Y, so \( Ext ( {\mathcal F}, l_0 ) \) has complement sparsity larger than a constant.
Therefore, the pairs (U. Y) such that \( Y \in {X \choose l} \) and \( U \in {\mathcal F} \cap {Y \choose m} \) play the central role again, so let’s give them a name. Imagining to put a checkmark on U when found in Y, let us call such a (U, Y) mark of Y. Denote the family of all marks by \( {\mathcal M} \) as Remark C) says on p.3-4 of Paper S3. It meets $$ |{\mathcal M} | = {n \choose l} {l \choose m} e^{-\kappa({\mathcal F})} = \sum_{Y \in {X \choose l}} \left| {\mathcal F} \cap {Y \choose m} \right|, $$ just as we figured it out in the 6/22 post, and Remark A) above C).
\( |{\mathcal M} | \) is fixed saying nothing on the topological properties of \( {\mathcal F} \). So we raise the dimension of U in set tuples from 1 to 2. A double mark of Y is a triple (U, V, Y) such that both (U, Y) and (V, Y) are marks of Y. Denoting their family by \({\mathcal D} \), we see two extreme cases:
In the first situation, the marks are completely distributed over all Y so \( |{\mathcal D}| = {n \choose l}{l \choose m}^2 e^{-2 \kappa({\mathcal F}) } \). In the second, there are \( {n \choose l} e^{-\kappa({\mathcal F}) } \) sets Y completely filled with the marks, so \( |{\mathcal D}| = {n \choose l}{l \choose m}^2 e^{- \kappa({\mathcal F}) } \). We could call the negative of the exponent of e sparsity of the double mark family \( {\mathcal D} \), which is always between \( \kappa ({\mathcal F}) \) and \( 2 \kappa ({\mathcal F}) \). The larger the sparsity is, the closer \( Ext ({\mathcal F}, l ) \) is proven to \( {X \choose l} \).
We want the sparsity closest to \( 2 \kappa({\mathcal F} ) \), and that’s what the double mark lemma on the bottom of p. 5 proves from the given \( \Gamma (b) \)-condition of \( {\mathcal F} \).
Links for mobile devices