Let’s have a look at the third critical point we talked about last time. It’s Step 2 of the proof of (2.1) on p. 8-9 of Paper 1. It’s good to just know the basic idea of how the third critical point works.

Recalling, we are in the recursive situation that:

We’re on the split pair \( {( \boldsymbol X}_*, {\boldsymbol X}’ ) \) having found an \(i-1\)-sunflower \( \{ Z_1, Z_2, \ldots, Z_{i-1} \} \subset \hat {\mathcal F}[C] \). Here \( \hat {\mathcal F} \) is the subfamily of \( {\mathcal F} \) detected by the preprocess including no elementary \( \hat \Gamma \)-subfamilies between \( \boldsymbol{X}_* \) and \( \boldsymbol{X}’ \), i.e., no \( {\mathcal T}_{B, \boldsymbol{X}’} \subset \hat {\mathcal F} \) such that B is an set on \( \boldsymbol{X}’ \) with |B|>r, satisfying the \( \Gamma(b) \)-condition on \( \boldsymbol{X}’ \setminus B \) where \( b = c k \log k\).

Precisely speaking, the \( \Gamma(b) \)-condition holds only within \( {\mathcal B}_{p-1} \), the family of base sets in \( Shd (\hat {\mathcal F} ) \cap {\boldsymbol{X}’ \choose m’ } \). As a minor adjustment of the second critical process, Step 1 eliminates some elements to try to achieve $$ (1) \qquad |{\mathcal Z}_C[U \cup B]| < (cb)^{-m’+r} |{\mathcal Z}_C[B]| \quad \textrm{for all} \quad U \in {\boldsymbol{X}’ \setminus \boldsymbol{X}_* \choose m’-r},$$ for each base set \( B \in {\mathcal B}_p \cap {\boldsymbol{X}_* \choose r} \). Let’s assume this is well-done.

Then we can further separate the red line segment \( Z_i \cap {\boldsymbol{X}’ \setminus \boldsymbol{X}_* \choose m’-r} – C \) to complete the current induction step (2.1) on page 6, which would lead to the detection of a k-sunflower eventually. Here’s how it works.

The family \( {\mathcal Z}_C[B] \) satisfies the \( \Gamma(b) \)-condition on \( \boldsymbol{X}’ \setminus \boldsymbol{X}_* \). Otherwise, there would be a nonempty set S on \( \boldsymbol{X}’ \setminus \boldsymbol{X}_* \) such that $$ |{\mathcal Z}_C[S \cup B]| \ge b^{-|S|} |{\mathcal Z}_C[B]|,$$ by definition. We know \( |S| \) cannot reach m’-r due to (1). So let’s take a maximal S with |S|<m’-r, i.e., $$ |{\mathcal Z}_C[U \cup S \cup B]| < b^{-|U \cup S|} |{\mathcal Z}_C[B]|,$$ for any nonempty set U on \( \boldsymbol{X}’ \setminus \boldsymbol{X}_* \setminus S \). By the two inequalities with \( B \in { \boldsymbol{X}_* \choose r }\), $$ |{\mathcal Z}_C[U \cup S \cup B]| < b^{-|U|} |{\mathcal Z}_C[S \cup B]|,$$ for all nonempty set U on \( \boldsymbol{X}’ \setminus (S \cup B) \).

This means \( {\mathcal Z}_C[S \cup B] \) would be an elementary \( \hat \Gamma (|S \cup B|,~{\mathcal B}_{p-1})\)-subfamily whose first parameter is greater than \(r=r_p \). The algorithm BaseSets had eliminated all such \( \hat \Gamma \)-families in the preprocess phase, so this situation is impossible to happen. By this contradiction, we know such a counter example S doesn’t exist, proving tthe \( \Gamma(b) \)-condition of \( {\mathcal Z}_C[B] \) on \( \boldsymbol{X}’ \setminus \boldsymbol{X}_* \).

Now we can separate the red line segment from \( {\mathcal Z}_C \). Let S be any singleton set included in it, so \( |{\mathcal Z}_C[S \cup B]| < b^{-1} |{\mathcal Z}_C[B]| \) for every base set \( B \in {\boldsymbol{X}_* \choose r} \) by the \( \Gamma \)-condition we’ve just shown. Further note that \( {\mathcal Z}_C[B]\) are mutually disjoint for all B, because B are r-sets existing on the unique r-subsplit \( \boldsymbol{X}_* \). Hence, $$ |{\mathcal Z}_C[S ]| < b^{-1} |{\mathcal Z}_C| .$$

Update \( {\mathcal Z}_C\) by eliminating \( {\mathcal Z}_C[S]\) to separate S, and it reduces \( {\mathcal Z}_C\) by less than its \( 1/b \). So we can separate the 2nd, 3rd ,…., \(m’-r\)th singleton sets S the same way, after each the same \( \Gamma \)-condition is available by the same argument. Finishing the separation of the red line in the end, we have more than \( (1-1/b)^{-m’+r} \) of the original \( {\mathcal Z}_C\) passing the cardinality requirement \( \Psi (p, i-1) \)-iii) on p. 6. This is how Step 2 is designed to prove (2.1).

Steps 2-4 of Paper 2 Ver 1 work essentially the same way, in the proof scenario posed in the 3/9 post: instead of separating an extra singleton set, add an extra strip to the current j-subsplit \( \boldsymbol{X}_j \) so the 3(=k) families \( {\mathcal F}_1, {\mathcal F}_2\), and \({\mathcal F}_3 \) are elementwise disjoint on the new j+1-subsplit \( \boldsymbol{X}_{j+1} \). It’s doable because in each step, the \(\Gamma(b)\)-condition of \( {\mathcal F}_i\) is available due to the prior removal of the \( \hat \Gamma \)-families with a larger r-parameter.

We’ll move to a new chapter to discuss how we can prove the EGT in the next few posts.

Links for mobile devices

• Index page
• Paper 1 Ver 1 (It has a major error that I am trying to fix now.)