Last time we proved Proposition 2.1 of Paper S4 for the smallest rank g=2. Although it itself is good to know, it doesn’t fill the gap between the regular and collective \( \Gamma \)-conditions too well. As noted in the 10/30 post, it’s necessary to raise the rank to a sufficiently large constant, so the gap is reduced to the factor \( m^{g/3} < m^\epsilon \). It’s our driving force to prove \( \Gamma( m^{\frac{1}{2}+\epsilon} ) \) \( \Rightarrow \) 3 mutually disjoint sets \( \in {\mathcal F} \).

So we generalize a double mark \( (U_1, U_2, Y ) \) into a \(g^{th} \) mark \[ ({\boldsymbol U}, Y), \quad \textrm{such that} \quad {\boldsymbol U}=(U_1, U_2, \ldots, U_g) \in {\mathcal F}^g, \quad \textrm{and} \quad Y \in {X \choose l} \cap {\mathcal F} \left[ \bigcup_{i=1}^g U_i \right]. \] To export a \(g^{th} \) collective \( \Gamma \)-condition, consider weight \( w: (2^X)^g \rightarrow {\mathbb R}_{\ge 0} \) as we did for g=2.

Then we think how we can achieve the goal essentially doing the same as g=2. We need:

1. A good definition of a \( \Gamma_g(b, h) \)-condition generalized from the \( \Gamma_2(b, h) \)-condition (20) in the 11/27 post.
2. Generalization of the double mark lemma provable from the \( \Gamma_g(b, h) \)-condition.
3. Proof that \( \Gamma(2b) \) of \( {\mathcal F} \) means the \( \Gamma_g(b, h) \).
4. A g-parameter weight w on \( {\mathcal F } \) to actually export the \(g^{th} \) collective \( \Gamma \)-condition.

Our solution here:

1. The \( \Gamma_g(b, h) \)-condition given in the first paragraph of p. 3 on the neighbor tuple family \( {\mathcal P}_{j, g} \) on p. 1.
2. The \(g^{th} \) mark lemma on p. 2.
3. The conversion lemma on p. 5. The base case of its inductive proof was partly used last time.
4. The weight w as set on p. 8. It’s a natural generalization of the weight used for g=2.

For g=2, we considered the (m-j)-neighbor pairs \( (U_1, U_2) \in {\mathcal P}_j \) such that \( |U_1 \cap U_2| = j \). Because of the given \( \Gamma(b) \)-condition, their largest density was about \( b^{-j} \) over the approximate maximum number \( e^{-2 \kappa({\mathcal F})} {n \choose m} {m \choose j} {n-m \choose m-j} \). The density was kept as low as \( 1 + (2 \gamma)^{-j} \) for \( {\mathcal D} \), by which we could prove the double mark lemma. We used that argument to export the 2nd collective \( \Gamma \)-condition last time.

If you increase g=2 to g=3, you have 8 partitioned subsets of X to deal with: \( U_1 \cap U_2 \cap U_3, ~U_2 \cap U_2 – U_3, \ldots \) etc. Each \( U_i \) is either included by \( \cap U_i \) or excluded by \( – U_i \), so there are \( 2^g= 8 \) partitioned subsets that could possibly appear in your proof. These highly depend on individual cases and are hard to argue in detail here.

But our discussions for g=2 just used \( U_1 \cup U_2 \) among the 4 partitioned subsets: the neighbor pair family \( {\mathcal P}_j \) includes those with \( |U_1 \cup U_2|=2 m-j \). As each of them produces exactly \( {n-2m+j \choose l-2m+j } \) double marks, we could manage to continue the argument to derive the upper bound on \( \| {\mathcal D} \| \).

Why don’t we do the same here with just one set \( Union ({\boldsymbol U} ) = \bigcup_{i=1}^g U_i \)? As g is constant despite it could be large, we can choose a \( \Gamma \)-parameter b sufficiently larger than \( 2^g \). This could absorb the complexity of those \( 2^g \) subsets.

That is why we define the neighbor tuple family for g to be \[ {\mathcal P}_{j, g} = \left\{ {\boldsymbol U} ~:~ {\boldsymbol U} \in {\mathcal F}^g,~ |Union({\boldsymbol U})| = gm- j \right\}. \] Also the \( \Gamma_g (b, h) \)-condition of \( {\mathcal F} \) is \[ \| {\mathcal P}_{j, g} \| < h b^{-j} \| {\mathcal F} \|^g, \quad \textrm{for all}~ j \in [m]. \] The more precise definition given on p. 2 comprises the two lines, but the first one is just to exclude anything not in \( {\mathcal F} \), which is consistent with our handlings so far.

By this we set up a good framework to enable all the 1-4 above.

Links for mobile devices

• Paper S4
• Paper 3
• Paper S3
• Index page

We are in the middle of confirming Proposition 2.1 of Paper S4 for the smallest rank g=2. Last time, we induced the norm \( \| \cdot \| \) from the 2-parameter weight w to define everything similar to before, including \( \kappa ( {\mathcal H} ) \), \( \| {\mathcal P}_j \| \), and \( \| {\mathcal D} \| \).

The newly introduced \( \Gamma_2(b, h) \)-condition means (20) looking similar to (3) in the 8/18 post, except for the coefficient \( h = |{\mathcal F}|^2 \| {\mathcal H} \|^{-2} \). We recall \( |{\mathcal D}| \) was tightly bounded by (4), because of the identity (6) to count double marks as we did in the 8/25 post.

If (20) is true, we’ll have (21) to successfully export the 2nd collective \( \Gamma \)-condition to the outside of \(X_* \). Let’s confirm the two in this post.

For (20):

This checks the truth of (20) combining the following two arguments: i) the base case of the proof of the Conversion Lemma in the first paragraph of p. 6 of Paper S4; ii) Remarks A)-C) on p. 8-9 particularly for g=2.

Then prove (21) by (20): \( \| {\mathcal D} \| \) can be expressed in \( \| {\mathcal P}_j \| \) as Remark A) of Paper S3 shown in the 10/8 post. Apply it to the same arguments of the 9/2 post with \( {\mathcal F} \rightarrow {\mathcal H} \), \( n \rightarrow n_* \), \( m \rightarrow m_* \), \( 1 \rightarrow h \) etc. Just as the generalization from the basic double mark lemma to its weighted case, the transition to the 2-parameter w here is mostly smooth.

However, one thing shouldn’t be dismissed about h. The argument only proves \[ \|{\mathcal D} \|<{n \choose l} {l \choose m}^2 e^{-2 \kappa({\mathcal F})} \left[ 1+ \frac{h}{2 \gamma} + \frac{h}{(2\gamma)^2} + \cdots + \frac{h}{(2\gamma)^m} \right]. \] It further takes h>1 to reach (21). It’s true thanks to the collective \( \Gamma \)-condition: the \( {\mathcal F} \) is given with the \( \Gamma( c b_*) \)-condition such that \( c b_*>2b \) as said in the figure. By Proposition 1-1 posed in the 10/30 post, the 2nd collective \( \Gamma(b, 1) \)-condition of \( {\mathcal F} \) is available. So, \[ \| {\mathcal H} \|^2 = \sum_{T \subset 2^{X-X_*} – \{ \emptyset \}} ~~ \frac{|{\mathcal F}[T]|^2}{b^{-|T|} {m \choose |T|}} < |{\mathcal F}|^2, \qquad \Rightarrow \qquad h = \frac{|\mathcal F|^2}{\| {\mathcal H} \|^2}>1, \] which confims (21).

Notice that:

Also \( \| {\mathcal D}\| = \sum_{Y \in {X_* \choose l}} ~~\sum_{T \subset 2^{X-X_*} – \{ \emptyset \}} \frac{| {\mathcal F}_Y [T] |^2}{b^{-|T|} {m \choose |T|}} \) from the last time. So a \( ( 1- \epsilon/10) \)-majority of l-sets Y satisfy the 2nd collective \( \Gamma(b, \epsilon^{-2} ) \)-condition in \( X – X_* \). Hence, a \( ( 1- \epsilon) \)-majority of Y indeed satisfy both the density requirement and exported collective \( \Gamma \)-condition.

We note that the quadratic optimization argument we made to prove Theorem 2.1 of Paper S3 doesn’t work for the 2-parameter weight w. Nevertheless, we have proven Proposition 2.1 of Paper S4 for g=2 with the new \( \| {\mathcal D} \| \).

Links for mobile devices

• Paper S4
• Paper 3
• Paper S3
• Index page

Last time, we found a good two-parameter weight (19) to export the \(g\)th collective \(\Gamma \)-condition to the outside of \( X_* \). For the smallest rank g=2, we are already mostly prepared to show Proposition 2.1. Let me clarify what we want to confirm.

• Given: \( X_* \in {X \choose n_*} \), and \( {\mathcal F} \subset {X \choose m} \) such that:
  • Every \( U \in {\mathcal F} \) intersects with \( X_* \) by the cardinality \( m_* = m n_* \big/ n \), or \( {\mathcal F} \subset Ext \left[ {X_* \choose m_*},~m \right] \).
  • \( {\mathcal F} \) satisfies the \( \Gamma( c m_* m^{\epsilon} ) \)-condition with \( cm_* m^{\epsilon}> 2b \).
• Show: a family \( {\mathcal Y} \subset {X_* \choose l} \) of l-sets Y in \(X_* \) such that:
  • \( l= \epsilon n_* \).
  • \( |{\mathcal Y}| > (1-\epsilon ) {n_* \choose l} \).
  • \( |{\mathcal F}_Y | > \frac{1}{2} {l \choose m_*} {n_* \choose m_*}^{-1} |{\mathcal F}| \), where \( {\mathcal F}_Y = {\mathcal F} \cap {X – X_* \cup Y \choose m} \).
  • \( \sum_{T \in 2^{X-X_*} – \{ \emptyset \} } \frac{| {\mathcal F}_Y [T] |^g}{b^{-|T|} {m \choose |T|}} < \frac{1}{\epsilon^2} | {\mathcal F}_Y |^g. \)

For simplicity, let’s say such a \({\mathcal Y} \) is a \( (1-\epsilon) \)-majority of all l-sets \( Y \in {X_* \choose l} \), and the rest an \( \epsilon \)-minority. The third condition is referred to as the density requirement. So, we want a \( (1-\epsilon) \)-majority of Y meeting the density requirement and exported collective \( \Gamma (b, \epsilon^{-2}) \)-condition. Here are how we can achieve them.

1. The Density Requirement. It’s done just the same as the 11/6 post with the single parameter weight \( w \) defined on \(X_* \): putting \[ {\mathcal H} = {X_* \choose m_*}, \] set \( w(U) = | {\mathcal F}[U] | \) for \( U \in {\mathcal H} \). Due to the given \( \Gamma( c m_*) \)-condition of \( {\mathcal F} \), the family \( {\mathcal H} \) satisfies the \( \Gamma( c m_*) \)-condition on the induced norm \( \| \cdot \| \). Then by Theorem 2.1 of Paper S3 and the complement sparsity lemma applied to \( {\mathcal H} \), we see a \( (1-\epsilon^2 ) \)-majority of Y meet the density requirement. This is essentially what Step 1 of Paper S4 does on p. 8 as well.

Please click the link to recall the argument in the 11/6 post. I think it’s pretty clear for us now.

2. The Exported Collective \( \Gamma \)-condition. Reset the weight \( w \) into (19) given last time. Define the induced norm \( \| \cdot \| \) by \[ \| {\mathcal U} \| = \left[ \sum_{{\boldsymbol U} \in {\mathcal U}^2} w ({\boldsymbol U}) \right]^{\frac{1}{2}}, \quad \textrm{for any } {\mathcal U} \subset 2^{X_*}, \] as on the first page of Paper S4. Just the same as we found \( w({\mathcal F}_Y) \) last time, \[ \| {\mathcal H} \|^2 = \sum_{(U_1, U_2) \in {\mathcal H}^2} w(U_1, U_2) = \sum_{T \subset X – X_,~T \ne \emptyset} ~~ \frac{|{\mathcal F}[T]|^2}{b^{-|T|} {m \choose |T|}}, \] \[ \Rightarrow \qquad \| {\mathcal H} \| = \sqrt{\sum_{T \subset X – X_,~T \ne \emptyset} ~~ \frac{|{\mathcal F}[T]|^2}{b^{-|T|} {m \choose |T|}}}. \]

With this norm \( \| \cdot \| \),:

The last line (20) is called the \( \Gamma_2 (b, h) \)-condition of \( {\mathcal H} \) that is slightly different from the version given on p.2 of Paper S4. They’re essentially the same, and we’ll confirm its truth next time.

This makes the situation practically no different from those parts of our proof of the EGT we dealt with before, except for \( {\mathcal F} \rightarrow {\mathcal H} \), \( n \rightarrow n_* \), \( m \rightarrow m_* \), \( 1 \rightarrow h \) etc. Use the same methods as the 9/2 post to prove the conclusion of the double mark lemma. This way we can see that:

So this norm of \( {\mathcal D} \) is the sum of the LHS of the target collective \( \Gamma \)-condition for all l-sets Y. Because it’s tightly bounded, most Y have the desired upper bound \( \sum_{T \in 2^{X-X_*} – \{ \emptyset \}} \frac{| {\mathcal F}_Y [T] |^2}{b^{-|T|} {m \choose |T|}} < \frac{1}{\epsilon^2} | {\mathcal F}_Y |^2 \). We’ll see more details of this next time.

Links for mobile devices

• Paper S4
• Paper 3
• Paper S3
• Index page

In this post, we start reviewing the new paper S4 to eventually prove its Proposition 2.1 we saw last time. Given an \( n_* \)-set \(X_* \) with \( m_* = m n_* / n \) in addition to \( {\mathcal F} \subset {X \choose m} \), our main motivation of the rank-g construction is not just to show there are a majority of \( Y \in {X_* \choose \epsilon n_*} \) such that \( {\mathcal F}_Y = {\mathcal F} \cap {X – X_* \cup Y \choose m} \) are reasonably dense (as in the 10/15 post and 11/19 post), but also to have each \( {\mathcal F}_Y \) satisfy the \(g^{th} \) collective \( \Gamma \)-condition. Let’s give it an initial thought about how we could achieve this feature we called export of the \( \Gamma \)-condition to \( X – X_*\).

Here we assume that every m-set \( U \in {\mathcal F} \) intersects with \(X_* \) by the cardinality \( m_* \). This can be safely presumed with the method 3 mentioned last time using Lemma A.1 on p. 10-12 of Paper S4. Paper S3 achieves this with a generalized split lemma also, but there is a simpler way. Paper S4 briefly mentions about it in the 4th paragraph of p. 7. We’ll discuss this in a later post.

With g=2 for simplicity, we look for a weight function w as follows:

Such a \( w \) can’t be defined on \( 2^{X_*} \). We can try \( w(U) = \alpha |{\mathcal F}[U]| \) and \( w(U) = \alpha |{\mathcal F}[U]|^2 \) for some coefficients \( \alpha>0 \) or others to see none of them works: it’s hard to correctly raise \( |{\mathcal F}_Y[T]| \) to the second power on the RHS of \( w ({\mathcal F}_Y ) \) with just one parameter of \( w: 2^{X_*} \rightarrow {\mathbb R}_{\ge 0} \).

However, it works if w is defined by \[ (19) \qquad w: 2^{X_*} \times 2^{X_*}\rightarrow {\mathbb R}_{\ge 0}, \qquad (U_1, U_2) \mapsto \sum_{T \subset X – X_*,~T \ne \emptyset} \frac{|{\mathcal F}[U_1 \cup T]| ~~ |{\mathcal F}[U_2 \cup T]|}{b^{-|T|} {m \choose |T|}}. \] Because with this two-parameter \(w \), each \( w ( {\mathcal F}_Y ) \) equals \[ \sum_{(U_1, U_2) \in {Y \choose m_*}^2} w(U_1, U_2) = \sum_{(U_1, U_2) \in {Y \choose m_*}^2} ~~ \sum_{T \subset X – X_,~T \ne \emptyset} \frac{|{\mathcal F}[U_1 \cup T]| ~ |{\mathcal F}[U_2 \cup T]|}{b^{-|T|} {m \choose |T|}} \] \[ = \sum_{T \subset X – X_,~T \ne \emptyset} ~~ \frac{|{\mathcal F}_Y[T]|^2}{b^{-|T|} {m \choose |T|}}, \] as required in the figure. Here \( {Y \choose m_*}^2 \) is a shorthand for \( {Y \choose m_*} \times {Y \choose m_*} \) working for other values of g and families the same way. The above is true because:

• \( |{\mathcal F}_Y[T]|^2 \) in the second line counts the number of pairs \( (V_1, V_2) \in {\mathcal F}_Y[T]^2 \).
• As assumed, it’s enough to consider all the \( m_* \)-subsets U of \( X_* \), and \( {\mathcal F}[U] \) that are mutually disjoint.
• So if you sum up \( |{\mathcal F}[U_1 \cup T]| ~ |{\mathcal F}[U_2 \cup T]| \) for each T and all \( (U_1, U_2) \in {Y \choose m_*}^2 \), you get \( |{\mathcal F}_Y[T]|^2 \), since every \( (V_1, V_2) \) is correctly counted just once in both.

Therefore, we need a g-parameter weight \( w: (2^{X_*})^g \rightarrow {\mathbb R}_{\ge 0} \) to be able to export a \(g^{th} \) collective \( \Gamma \)-condition. That’s why we want the rank g as the first page of Paper S4 defines.

Links for mobile devices

• Paper S4
• Paper 3
• Paper S3
• Index page

Last time, we saw by the EGT that \( {\mathcal F} \) with \( \Gamma(c m~k \ln k ) \) includes k reasonably large elementwise disjoint subfamilies achieving the complete separation from each other. The methodology Paper 3 presents can improve it into the following unwritten statement.

Proposition 3. A family \( {\mathcal F} \subset {X \choose m} \) satisfying the \( \Gamma(c m^{\frac{1}{2}+\epsilon}~k \ln^2 k ) \)-condition includes elementwise disjoint subfamilies \( {\mathcal F}_1, {\mathcal F}_2, \ldots, {\mathcal F}_k \) such that \[
{\mathcal F}_i \subset {\mathcal F}[C_i], \qquad \textrm{and} \qquad
|{\mathcal F}_i| > (cm^{\frac{1}{2}+\epsilon}~k \ln^2 k)^{-|C_i|} (8 k \ln^2 k)^{-m+|C_i|} |{\mathcal F}|.
\] Here \( \epsilon>0 \) is any given small number, c>0 is sufficiently larger than \( 1 / \epsilon \), and \( C_1, C_2, \ldots, C_k\) are some mutually disjoint k sets each with \( |C_i| < m/ c \).

So such an \( {\mathcal F} \) for k=3 includes 3 mutually disjoint sets rather than just a 3-sunflower. The constant c of the \( \Gamma \)-condition can be omitted if we know m is large enough.

It takes three critical methods to prove the proposition.

1. Rank-g construction: Section 2 on p. 3-6 of Paper 3, and Steps 2 and 3 of its main construction on p. 15-19.
2. Push-up lemma: Step 6 on p. 20-22.
3. Initial growth of the local cores \( C_i \): Section 3 on p. 9-12 about generalizing the split lemma, the preprocess given on p. 12-14, and Lemma A.3 on p. 24-25.

The most important of the three is the first one, the rank-g construction. To explain it, I’ve uploaded the new supplementary paper S4 on the left. Please click the link to take a look. It explains the essence of Method 1 proving Proposition 2.1 on its page 7. Let me restate its description with a given sufficiently small constant \( \epsilon>0 \), \[ c= \exp(\epsilon^{-1} ), \quad n_* \in [n], \quad m_* = \frac{mn_*}{n}, \quad \textrm{and} \quad b = c m_* m^{\epsilon}. \]

Proposition 2.1 of Paper S4. Let \( {\mathcal F} \subset {X \choose m} \) satisfy the \( \Gamma( 2 b ) \)-condition. There exist more than \( (1-\epsilon) {n \choose n_*} \) sets \( X_* \in {X \choose n_*} \), in each of which there are \( (1-\epsilon) {n_* \choose \epsilon n_*} \) subsets \( Y \in {X_* \choose \epsilon n_*} \) satisfying the following condition: the family \({\mathcal F}_Y = {\mathcal F} \cap {X- X \cup Y \choose m} \) meets \( | {\mathcal F}_Y| > \epsilon^{2 m_*} |{\mathcal F}| \) and the \(g^{th} \) collective \( \Gamma( b, \epsilon^{-2} ) \)-condition in \( X – X_* \).

Here the collective \( \Gamma \)-condition in \( X – X_* \) is unweighted referring to \[ \sum_{u \in [m],~T \in {X- X_* \choose u}} \frac{| {\mathcal F}_Y [T] |^g}{b^{-u(g-1)} {m \choose u}} < \frac{1}{\epsilon^2} | {\mathcal F}_Y |^g. \] The given \( \Gamma(2b) \)-condition means the collective \( \Gamma(b, 1) \)-condition of \( {\mathcal F} \) in X as we saw in the 10/23 post. So this does not just guarantee a majority of reasonably dense \( {\mathcal F}_Y \) in \( X_* \), but also exports the collective \( \Gamma \)-condition of each \( {\mathcal F}_Y \) to the outside of \( X_* \) up to the error factor \( \epsilon^{-2} \).

This helps our recursive arguments on \( X_1, X_2, \ldots, X_r \subset X \) a lot. In the 3/9 post, we saw such a proof scenario would have the difficulty in guaranteeing the necessary \( \Gamma \)-condition in the next step from \( X_i \). It is a part of the very elusive difficulty hidden in sunflowers. By exporting the collective \( \Gamma\)-condition by the rank-g construction, we can resolve this issue fundamentally as long as \( r < m^{\frac{1}{2} – \epsilon} \).

To void the extra error factor \( \epsilon^{-2} \), the recursive process at \( X_i \) grows each local core \( C_i \) by the push-up lemma in Step 6. It’s a variant of the simple core growth to have the \( \Gamma(b) \)-condition of \( {\mathcal F}_i [C_i] \) in \( X – C_i \). The lemma is designed for the collective \( \Gamma \)-condition rather than the regular \( \Gamma \)-condition. The process doesn’t repeat indefinitely, at most \( r < m^{\frac{1}{2} – \epsilon} \) times requiring \( b > m^{\frac{1}{2} + \epsilon} \).

Starting next time, we’ll see the details of the rank-g construction to eventually prove Proposition 2.1.

Links for mobile devices

• Paper S4
• Paper 3
• Paper S3
• Index page

Our second proposition as another motivation remark is the following.

Proposition 2. For any family \( {\mathcal F} \subset {X \choose m} \) satisfying the \( \Gamma(c m~k \ln k) \)-condition (\(k \in {\mathbb Z}_{>1} \) and c>1 sufficiently large), there exist k subfamilies \( {\mathcal F}_1, {\mathcal F}_2, \ldots, {\mathcal F}_k \subset {\mathcal F} \) that are elementwise disjoint, i.e., \(U \cap U’ = \emptyset \) for any \( U \in {\mathcal F}_i \) and \( U’ \in {\mathcal F}_{i’} \) with \( i \ne i’ \), such that \( |{\mathcal F}_i| > \left( \frac{1}{8k \ln k} \right)^m |{\mathcal F}| \).

We dealt with the elementwise disjointness in the 3/9 post. Considering that the given condition \( |{\mathcal F}| > (k-1)^m m! \) of the sunflower lemma is practically the \( \Gamma \left( km \big/ e \right) \)-condition (the 2/3 post), we’re seeing that if you raise the b value of the \( \Gamma \)-condition by the factor of \( \ln k \) times a constant, you can find k reasonably large elementwise disjoint subfamilies of \( {\mathcal F} \), achieving the complete separation from each other. It’s a fact good to know.

The statement is actually a corollary to Theorem 2.1 of Paper S3 and the complement sparsity lemma, so it’s an application of the EGT. With \( \epsilon = 1 \big/ \ln c \), and \( l = n \Big/ 4 k \ln k \), apply the theorem to \( {\mathcal F} \) to see that there are \( (1- \epsilon ) {n \choose l} \) sets \( Y \in {X \choose l} \) such that \[ |{\mathcal F}_Y| > (1-\epsilon) \frac{{l \choose m}}{{n \choose m}} |{\mathcal F}| > \left( \frac{l}{2n} \right)^m |{\mathcal F}| = \left( \frac{1}{8 k \ln k} \right)^m |{\mathcal F}|, \qquad \textrm{where} \quad {\mathcal F}_Y = {\mathcal F} \cap {Y \choose m}. \] Here you can check \( (1- \epsilon) {l \choose m}{n \choose m}^{-1} > \left( l \big/ 2n \right)^m \) the same way as we did sometimes before.

Extend the family \( {\mathcal Y} \) of Y into \( {\mathcal Y}’ = Ext \left( {\mathcal Y}, l’ \right) \) where \( l’ = n \big/ (2k) \). By the complement sparsity lemma, \( \kappa \left[ {n \choose l’ } – {\mathcal Y}’ \right] > 2 \ln k \), meaning \( |{\mathcal Y}’| > \left( 1 – \frac{1}{2k} \right) {n \choose l’} \).

As this \( {\mathcal Y}’ \) forms a majority of \( {X \choose l’} \) with that complement sparsity, we can find k mutually disjoint sets \( Y’_1, Y’_2, \ldots Y’_k \in {\mathcal Y}’ \) similarly to the extra notes of the 2/23 post: there are \( {n \choose l’} {n -l’ \choose l’} \cdots {n – (k-1) l’ \choose l’} \) set tuples \( (Y’_1, Y’_2, \ldots, Y’_k) \) in total such that l’-sets \( Y’_i \) are mutually disjoint. Only less than \( 1 \big/ 2k \) of them may have a particular \( Y’_i \) not in \( {\mathcal Y}’ \). Removing those bad tuples for any \( Y’_i \), we have a remaining half with good \( Y’_i \) only. Pick up any one of them, and the sets \( Y’_1, Y’_2, \ldots Y’_k \) are mutually disjoint all in \( {\mathcal Y}’ \).

Each such \( Y’_i \) includes an l-set \( Y_i \in {\mathcal Y} \) for which we have constructed the subfamily \( {\mathcal F}_{Y_i} \) above. Put \( {\mathcal F}_i = {\mathcal F}_{Y_i} \) finishing the construction. Because \( Y’_1, Y’_2, \ldots Y’_k \) are mutually disjoint, so are \( Y_1, Y_2, \ldots Y_k \). Therefore, \( {\mathcal F}_1, {\mathcal F}_2, \ldots, {\mathcal F}_k\) are elementwise disjoint.

After staring at the proposition, it’s natural to wonder if we can bring down the factor m of the \( \Gamma \)-condition to something much smaller. It is the very motivation of having the sunflower conjecture from the sunflower lemma. For that purpose, we want to partition X into \( X_1, X_2, \ldots, X_r \), within each of which we do similar operations using the weighted EGT. This is a common proof scenario in this study as said in the 2/23 post.

The rank-g construction with a collective \( \Gamma \)-condition will be seen useful for such a scenario. I’ll post another paper for this including the last opening proposition before next time. We’ll look into its details for a while.

Links for mobile devices

• Index page
• Paper 3
• Paper S3

We’ll see three propositions as the opening remarks of this topic. As the first one, we’re checking:

Proposition 1.

1. If \({\mathcal F} \) satisfies the \( \Gamma(b) \)-condition on the norm \( \| \cdot \| \), then both (16) with \( b \leftarrow b / m \), and (17) with \( b \leftarrow b/2 \) and h=1 hold true.
2. If (16), there exists a subfamily \( {\mathcal F}’ \subset {\mathcal F} \) satisfying \( \| {\mathcal F}’ \| > 2^{-1} \| {\mathcal F} \| \) and the \( \Gamma \left( b / 6 \right) \)-condition on \( \| \cdot \| \).
3. If (17) for a given \( g>1 \), \( b< m^2\), and \( h=1 \), the family \( {\mathcal F} \) satisfies the \( \Gamma \left( b m^{-3/g} \right) \)-condition on \( \| \cdot \| \).

It was given last time essentially saying the three \( \Gamma \)-conditions are similar depending on the choice of b, h and \( \gamma \). Let’s finish justifying it.

Prop. 1-3 is found true as follows. If \( {\mathcal F} \) doesn’t satisfy the \( \Gamma \left( b m^{-3/g} \right) \)-condition on \( \| \cdot \| \), there exists a nonempty set T of cardinality u such that \( \| {\mathcal F}[T] \| \ge ( b m^{-3/g} )^{-u} \| {\mathcal F} \| \), so $$
\sum_{T \in {X \choose u}} | {\mathcal F}[T] |^g > \left( \frac{b}{m^{3/g}} \right)^{-ug} | {\mathcal F} |^g > b^{-u(g-1)} m^u | {\mathcal F} |^g > b^{-u(g-1)} {m \choose u} | {\mathcal F} |^g,
$$ whose second inequality is due to \( b< m^2 \). This falsifies (18) last time, and also (17), impossible to hold true. Hence (17) means the \( \Gamma \)-condition of \( {\mathcal F} \).

To show Prop. 1-2, we want to construct a large enough subfamily \( {\mathcal F}’ \subset {\mathcal F} \) satisfying the \( \Gamma(b/6) \)-condition from (16). Copy \( {\mathcal F} \) into \({\mathcal F}’ \) and try u=|T|=1 first: find a singleton set \( T \in {X \choose u} \) such that \( \| {\mathcal F}'[T] \| \ge (b/3)^{-u} \| {\mathcal F} \| \). If found, delete the \( {\mathcal F}'[T] \) from \( {\mathcal F}’ \). Continue until such a T is no longer detected.

This reduces less than \( 3^{-u} \) of the total norm \( \| {\mathcal F} \| \), otherwise it finds such a u-set \( \frac{3^{-u} | {\mathcal F} | }{(b/3)^{-u} | {\mathcal F} |} = (b/9)^u \) times or less to cause this contradiction: $$ \sum_{T \in {X \choose u}} \| {\mathcal F}[T] \|^2 \ge \left( \frac{b}{9} \right)^u \left[ \frac{\left\| {\mathcal F} \right\|}{(b/3)^u} \right]^2 = b^{-u}\left\| {\mathcal F} \right \|^2, $$ falsifying (16). The inequality in the middle is exactly seen by the optimization problem (10) we talked about in the 9/17 post. It’s true because the solution to (10) is \( A^2 / N \).

Do the same for u=2, 3, 4, \( \ldots \), for each of which we eliminate less than \( 3^{-u} \) of \( \| {\mathcal F} \|. \) In the end we have the remaining \( 1 – 3^{-1} – 3^{-2} – \cdots > \frac{1}{2} \) with no T meeting \( \| {\mathcal F}’ [T] \| \ge (b/3)^{-|T|} \| {\mathcal F} \| \). Therefore, the obtained \( {\mathcal F}’ \) is more than a half of \( {\mathcal F} \) satisfying the \( \Gamma (b/6) \)-condition, finishing the proof.

We now notice a fact motivating the rank-g construction mentioned last time. If we use (16) with the collective \( \Gamma(b) \)-condition of rank 2, the b is actually equivalent to bm for the basic \( \Gamma \)-condition as seen in Prop. 1-1. If we can use (17) in a proof, the gap between the two is about \( m^{3/g} \) or less, which is a lot smaller than m if g is a sufficiently large constant. The main result of Paper 3 is \( \Gamma \left( m^{\frac{1}{2} + \epsilon} \right) \) meaning three mutually disjoint sets in \( {\mathcal F} \) as has been said. That \( \epsilon \) comes from the \( 3/g \) here.

Additionally, (16) with \( b = 5 \gamma m n / l \) alone means the claims of the double mark lemma and Theorem 1.2 of Paper S3 in the weighted case. You can check it with the same arguments in the 8/18 post, where we see $$ \sum_{T \in {X \choose j}} \|{\mathcal F}[T] \|^2 < b^{-j} \| {\mathcal F} \|^2, \qquad \Rightarrow \qquad \| {\mathcal P}_j \| \le \left( \frac{m}{b} \right)^j \| {\mathcal F} \|^2. $$ Apply this to the discussion in the 9/2 post and others.

Links for mobile devices

• Index page
• Paper 3
• Paper S3

In this post, we start exploring our new topic, the collective \( \Gamma \)-conditions. On the weighted domain \( 2^X \) with the induced norm \( \| \cdot \| \), the simple one states $$ (16) \qquad \sum_{T \in {X \choose j}} \|{\mathcal F}[T] \|^2 < b^{-j} \| {\mathcal F} \|^2, \quad \textrm{for all}~ j \in [m], $$ which is equivalent to its unweighted version (5) given in the 8/18 post if \( b=5 \gamma n/ l \). It implicitly assumes the 2nd condition \( U \not \in {\mathcal F} \) \( \Rightarrow \) \( w(U)=0 \) whenever necessary.

The rank of the \( \Gamma \)-condition is 2 because it takes the 2nd power inside. The primary benefit of considering a collective \( \Gamma \)-condition is that we can raise the rank to a sufficiently large constant g to enhance the depth of arguments significantly. As we noted this in the 8/4 post, Paper 3 posted on the left uses the rank g to prove \( \Gamma( m^{\frac{1}{2}+\epsilon}) \) of \( {\mathcal F} \) means there are three mutually disjoint sets in \( {\mathcal F} \), not just a 3-sunflower, for any given small constant \( \epsilon>0 \) and sufficiently large m.

For the next while, we’ll see the essence of the Paper 3 construction: what the \(g^{th} \) mark lemma, Lemma 2.1 on p. 3 does and how it’s proven, also how it is connected to our previous discussions and is used in the proof the 3-disjoint-sets claim. We’ll focus on the intrinsic ideas behind dismissing some details, in order to convince us that the rank-g argument works. It’ll take some time for it.

To use a collective \( \Gamma \)-condition in the proof in Section 4.2, it’d be most useful if provided as a single inequality. Rather than the form of (16), we define the \(g^{th} \) collective \( \Gamma(b, h) \)-condition of \( {\mathcal F} \subset {X \choose m} \) as $$ (17) \qquad \sum_{u \in [m],~T \in {X \choose u}} \frac{\| {\mathcal F} [T]\|^g}{b^{-u(g-1)} {m \choose u}} <h \| {\mathcal F} \|^g, $$ where b>0 is typically \( \gamma n m / l \) as before, and h>0 is a sufficiently large constant given for proof convenience. A variant of this form is used as the condition \( \Pi_j\)-ii)-a) on p. 14 to be maintained recursively by the main proof.

First off, let’s show that the plain \( \Gamma (\gamma m n / l) \)-condition we’ve been investigating for the proof of EGT is roughly the same as (16) and (17), with proper choices of b, h and sufficiently large \( \gamma \). (Please recall n=|X| and l is the target extension length, i.e., the 2nd parameter of \( Ext ({\mathcal F}, l) \).) We check the three statements.

Proposition 1.

1. If \({\mathcal F} \) satisfies the \( \Gamma(b) \)-condition on the norm \( \| \cdot \| \), then both (16) with \( b \leftarrow b / m \), and (17) with \( b \leftarrow b/2 \) and h=1 hold true.
2. If (16), there exists a subfamily \( {\mathcal F}’ \subset {\mathcal F} \) satisfying \( \| {\mathcal F}’ \| > 2^{-1} \| {\mathcal F} \| \) and the \( \Gamma \left( b / 6 \right) \)-condition on \( \| \cdot \| \).
3. If (17) for a given \( g>1 \), \( b< m^2\), and \( h=1 \), the family \( {\mathcal F} \) satisfies the \( \Gamma \left( b m^{-3/g} \right) \)-condition on \( \| \cdot \| \).

By Prop. 1-1, we are given \({\mathcal F} \) such that \( \| {\mathcal F}[T] \| < b^{-|T|} \| {\mathcal F} \|\) for every nonempty set T. So $$ (18) \qquad \sum_{T \in {X \choose u}} \| {\mathcal F}[T] \|^g < b^{-u(g-1)} {m \choose u} \| {\mathcal F} \|^g, \qquad \textrm{for all}~ u \in [m], $$ for the integer g given by (17). Think of it this way: if \( \| \cdot \| \) is just the cardinality \( | \cdot | \) and g=2, the sum \( \sum_{T \in {X \choose u}} \| {\mathcal F}[T] \|^2 \) counts set pairs \( (U_1, U_2) \) with \( U_i \in {\mathcal F}[T] \), so the RHS should be \( b^{-u} {m \choose u} |{\mathcal F}|^2 \) as correctly given there.

For any norm and \( g \ge 2 \), the LHS considers all the set tuples \( (U_1, U_2, \ldots, U_g) \) with \( U_i \in {\mathcal F}[T] \), finding the product of \( \| {\mathcal F}[U_i] \| \). To upper-bound \( \sum_{(U_1, U_2, \ldots, U_G)} \prod_{i \in [g]} \| {\mathcal F}[U_i] \| \), fix any \(U_1\) so the first factor is \( \|{\mathcal F}\| \). There are \( {m \choose u} \) choices of \( T \in {U_1 \choose u} \), for each of which all \( U_2 \in {\mathcal F} [T] \) produces the factor \( \| {\mathcal F}[T] \| < b^{-u} \| {\mathcal F} \| \). So we multiply \( \|{\mathcal F}\| {m \choose u} \) by \( b^{-u} \| {\mathcal F} \| \). Do the same for \( U_2, U_3, \ldots, U_g \) to get (18).

This means $$ \sum_{T \in {X \choose u}} \frac{\| {\mathcal F}[T] \|^g}{(b/2)^{-u(g-1)} {m \choose u}} < 2^{-u} \| {\mathcal F} \|^g, \qquad \textrm{for}~ u \in [m]. $$ Summing this up for all u, we see \( \Gamma(b) \) of \( {\mathcal F} \) \( \Rightarrow \) (18) with \( b \leftarrow b/2 \) and \( h \leftarrow 1 \), confirming the second statement of Proposition 1-1.

The first statement of P 1-1 is simpler to see: with \( g \leftarrow 2 \) in (18), $$ \sum_{T \in {X \choose u}} \| {\mathcal F}[T] \|^2 < b^{-u} {m \choose u} \| {\mathcal F} \|^2 < \left( \frac{b}{m} \right)^u \| {\mathcal F} \|^2, $$ justifying (16) with \( b \leftarrow b/m \).

We’ll continue on the proof next time.

Links for mobile devices

• Index page
• Paper 3
• Paper S3

Having proven Corollary 3.2 of Paper S3 last time. it remains to confirm Theorem 2.1 on p. 4 and figure out the unwritten weighted EGT before we finish this topic. The main difference between the two is the weight function considered by the theorem: put any weight \( w(U) \ge 0 \) for all \( U \in {\mathcal F} \) to define the weighted \(\Gamma \)-condition, true if and only if \( w({\mathcal F}[S]) < b^{-|S|} w({\mathcal F})\) for any nonempty set S. Here w(family) means the sum of weight of all the elements included in the family. According to Theorem 2.1, if \( {\mathcal F} \) satisfies this \( \Gamma \)-condition with \( b = 5 \gamma mn/l \), almost every l-set Y has approximate weight \( w({\mathcal F}) {l \choose m} \Big/ {n \choose m} \), just as the corollary says for the unit weight that is practically the cardinality.

This is absolutely necessary in this study where the universal set is usually partitioned evenly into \( X_1, X_2, \ldots, X_r \) as said in the 2/27 post, in each of which we try to show some properties using the EGT and other tools. If the EGT didn’t support weight, it wouldn’t be useful because the final goals would never be about cardinalities within each \( X_i \).

Formally, a general weight function should be given just as \( w: 2^X \rightarrow {\mathbb R}_{\ge 0} \) (meaning \( w(U) \ge 0 \) for any set U) for generality, while the extra essential condition \( U \not \in {\mathcal F} \) \( \Rightarrow \) \( w(U)=0 \) is better contained in the \( \Gamma \)-condition. There it helps to define the norm and weighted sparsity of any family \( {\mathcal G} \subset 2^X \) as $$ \left\| {\mathcal G} \right\| = \sum_{U \in {\mathcal G}} w(U), \qquad \textrm{and} \qquad \kappa ( {\mathcal G} ) = \ln {n \choose m} – \| {\mathcal G} \|, $$ respectively, as on p. 3. They are \( | {\mathcal G} \cap {\mathcal F}| \) and the regular unweighted sparsity if the weight is unit with respect to \( {\mathcal F} \), i.e., w(U)=1 if \( U \in {\mathcal F} \) and w(U)=0 otherwise.

In addition, the families \( {\mathcal M} \) of marks, \( {\mathcal D} \) of double marks, and \( {\mathcal P}_j \) of (m-j)-neighbor pairs are given the following norms:

Then they satisfy the same relations as the unweighted case. For example, in Remark A), the norm of \({\mathcal M} \) is \( \| {\mathcal F} \| {n-m \choose l-m} = {n \choose l} {l \choose m} e^{-\kappa({\mathcal F})} \) because each \( U \in {\mathcal F} \) constributes w(U) to \( {n-m \choose l-m} \) sets \( Y \in {X \choose l} [U] \).

Also the weighted \( \Gamma(b) \)-condition can be formally defined as $$ (15) \qquad \| {\mathcal P}_j \| < \| {\mathcal F} \|^2 b^{-j} {m \choose j}~\textrm{for all}~ j \in [m], \qquad \textrm{and} \qquad U \not \in {\mathcal F} \Rightarrow w(U)=0, $$ just the same as (3) in the 8/18 post, and page 3 on Paper S3.

This way the generalization to the weighted case is surprisingly smooth. There are almost nowhere to fix after changing \( \left| {\mathcal F} \cap {Y \choose m} \right| \) to \( \left\| {Y \choose m} \right \| \), and the other \( | \cdot | \) to \( \| \cdot \| \).

Links for mobile devices

• Index page
• Paper S3