Last time, we found a contradiction in Case 1 defined by (3.1) on 9/16/24. It remains to do the same for Case 2 with (3.2) to finish the proof.
Use (4.1) and (4.2) like (3.1) and (3.3) on 9/16/24 to show a similar contradiction. We’ll do it next time to finish the proof.
Links for mobile devices
We continue to prove the push-up lemma. We want to show (3.4) found last time implies (3.5).
We’ve been trying to find a contradiction in Case 1 defined by (3.1) last time. And it’s done: we have (3.5) by (3.4) and (3.4) \( \Rightarrow \) (3.5) we just confirmed. But it’s equal to the negative of the given condition (2.1), impossible to be true. (See (2.1) on 8/26/24 and 9/9/24.)
We’ll find a contradiction in Case 2 to finish the proof in the next two posts.
Links for mobile devices
We started proving the push-up lemma by contradiction last time, falsely assuming there’s no \( v \)-set \(S \) such that 1) \( \wedge \) 2) \( \wedge \) 3). It turned out it would complete the proof if we find a contradiction in (2.4).
We’ll confirm (3.4) \( \Rightarrow \) (3.5) next time, so we’ll know Case 1 is impossible to happen.
Links for mobile devices
Let’s start proving the push-up lemma. Given \( \mathcal{F} \) satisfying the \(g^{th} \) collective \( \Gamma \)-condition \[ (2.1) \qquad \sum_{u_* \le u \le m,~S \in {X \choose u}} ~\frac{\| \mathcal{F} [S] \|^g}{b^{-(g-1)u} {m \choose u}} < h \| \mathcal{F} \|^g, \] we want to show some set \( S \) with \( 0 \le |S| <u_* \) meets the three conditions 1)-3) given on 8/26/24.
There \( u_* \) is the given lower bound on \( u \), which can be the \( cr \) of the condition \( \Pi(j)\)-iii) we saw last time. By the nature of the proof, it’s better to partition the collective \( \Gamma \)-condition into the two parts \( u \ge u_* \), and \( u< u_* \). We’ll see its reason more clearly soon.
Please click the link to the 2/26/24 post to recall the multiplicative \( g \)-parameter weight we used to prove Proposition 2.1 of Paper S4. We continue on the proof next time.
Links for mobile devices
Last time, we formulated the push-up lemma seeing how it can help void the extra constant factor \( \epsilon^{-2} \) to start the second step on \( X_2 \). Let’s get convinced it’s good for any \( X_i \) and \( C_i \) in our forthcoming proof of the three-disjoint-set claim. Keeping focusing on the case \( k=3 \), we want to prove the following statement like 7/29/24 for Theorem 6:
Then we do the simultaneous core growth like 7/29/24: apply the push-up lemma to \( \mathcal{F}_1 \) with the first condition of C) to achieve \( \Pi(j+1) \)-iii) & iv) for \( \mathcal{F}_1 \). This grows the core \( C_1 \) by a set \( S_1 \) such that \( |S_1| < cr \). Also due to the second line of C), \[ |\mathcal{F}_i [S] | < \epsilon^{-2/g} \left( \frac{b_j}{4} \right)^{1 – g^{-1}} {m \choose u}^{1/g} |\mathcal{F}_i| < \frac{m^{\epsilon^3}}{b_j} |\mathcal{F}_i| < \frac{r}{m} |\mathcal{F}_i|, \] for \( i=2, 3 \) and all \( S \in {Z_j – X_j \choose 1} \). So we can remove \( \mathcal{F}_1[S_1] \) from \( \mathcal{F}_i \) without much disturbing their C), allowing for the same core growth for the remaining two \( \mathcal{F}_i \).
This way we’ll be able to show all the conditions of \( \Pi(j+1) \). As \( \Pi(r) \) means three mutually disjoint sets in \( \mathcal{F} \), we can now tell that the push-up lemma will help us prove the three-disjoint-set claim.
Links for mobile devices
Please recall the three methods mentioned on 11/13/23. We are now familiar with the 1st and 3rd ones and will be with all the three after this subchapter, ready to verify the three-disjoint-set claim. We discussed the necessity of the push-up lemma last time – it allows for the simultaneous core growth staying on the \( g^{th} \)-collective \( \Gamma \) condition, without which accumulated constant overheads will eventually overwhelm the entire construction.
This is how the lemma is formulated:
In the rest of the post today. we overview how the lemma helps finalize the first induction step on \( X_1 \) of \( \boldsymbol{X} \) for the three-disjoint-set claim.
We continue the overview next time
Links for mobile devices
We finished the subchapter to discuss splits of \(X \) last time. In this new chapter, we’ll find all the details of how we can prove the three-disjoint-set claim exactly. We’ll eventually confirm Proposition 3 on 11/13/23 for a general \( k \) to even try pushing the bound to the limit. I plan to include the obtained findings in the next version of Paper 2.
Let’s figure out its proof scenario for \( k=3 \) continued from 4/29/24. Initially, we’re just given an \( {\mathcal F} \) with the \( \Gamma(b) \)-condition where \( b=m^{\frac{1}{2} + \epsilon} \) for an \( m \) sufficiently larger than \( \epsilon^{-1} \). We can without loss of generality replace \( \epsilon \) by \( 2 \epsilon \) to let the constant \( c \) be the minimum possible value of \(m^{\epsilon} \). Then \[ b= c m^{\frac{1}{2} + \epsilon} \] with the large constant \(c \), for which we want to prove such an \( \mathcal{F} \) includes three mutually disjoint sets. This is what Theorem 1.1 of Paper 3 claims.
Further putting \[ r= m^{\frac{1}{2} – \epsilon^2} \] as before, apply Theorem 6 on 7/29/24 to \( \mathcal{F} \), \( b \), \( c \), \(r \) and \( k=3 \). This produces three sets \( C_i \), subfamilies \( \mathcal{F}_i \subset \mathcal{F}[C_i] \), and an \(r \)-split \( \boldsymbol{X} \) that are good for the rank \(g \)-construction. Especially, \( C_i \) are mutually disjoint meeting \( |C_i| < m^{1-\epsilon} \), and \( \mathcal{F}_i \) satisfy \( \Gamma(b/2) \), or just \( \Gamma (b) \) without loss of generality.
Now we perform the rank-\(g\) construction for all three \( \mathcal{F}_i \) on the first strip \(X_1\) of \( \boldsymbol{X} \). Please go through the three steps on p. 8-10 of Paper S4 again to recall what we did in Chapter 3 discussing collective \( \Gamma \)-conditions:
Then like 11/6/23, consider all the triples \( (Y_1, Y_2, Y_3 ) \in {X_1 \choose l}^3 \) where \( Y_i \) are the \( Y \) of \( \mathcal{F}_i \) disjoint with the other two. We know that for a vast majority of \( (Y_1, Y_2, Y_3) \), each \( \mathcal{F}_{i, Y_i} \) satisfies both the density requirement and exported \( \Gamma \)-condition, so we can find and fix such a good \( (Y_1, Y_2, Y_3 ) \). Then:
But something is missing before the process is quite complete. It’s about the constant overhead in Step 3: in the second figure of 4/8/24, the LHS of the collective \( \Gamma \)-condition is not bounded by \( |\mathcal{F}_Y|^g \) but by \( \epsilon^{-2} |\mathcal{F}_Y|^g \). If such a constant overhead is allowed accumulated for \( r \) steps, the LHS of the final collective \( \Gamma \)-condition would be bounded by \( \epsilon^{-2 r} |\mathcal{F}_Y|^g \), which compromises the recursive process totally.
We could think of reconstructing the collective \( \Gamma \)-condition for the second step: from the exported \( \Gamma \)-condition, extract a plain \( \Gamma(b_2) \)-condition for some \( b_2 \) close to \( b \) to do the simultaneous core growth like we did on 7/29/24 and after it. Then reconstruct a collective condition from the obtained \( \Gamma (b_2 ) \)-condition.
However, please see Proposition 1 on 10/23/24, where we could obtain the collective \( \Gamma( b/2, 1) \)-condition from the given \( \Gamma(b) \)-condition. A constant factor overhead can’t be helped that way either.
So we need a way to perform simultaneous core growth staying on a given collective \( \Gamma \)-condition. The push-up lemma is designed to achieve this goal in an interesting way. It’s practically Step 6 on p. 20-22 of Paper 3. We’ll formulate it next time.
Links for mobile devices
We have resolved our initial core growth problem last time by proving Theorem 6 given on 7/29/24. With the statement, we can convert an \( {\mathcal F} \) from Proposition 3 on 11/13/23 into \( k \) families \( {\mathcal F}_i \) on the same \(r \)-split \( \boldsymbol{X} \), each satisfying almost the same \( \Gamma \)-condition as the original. This will allow for the rank \( g \)-construction \( r \) times on \( {\mathcal F}_i \) for our confirmation of the three-disjoint-set claim. It’s been another good step toward it.
There is an interesting remark about Theorem 5 on 7/22/24 related to the complexity of computing the clique function. It was our very first topic to start this blog series given on 1/21/23 and 1/27/23. Please click the two links to recall what we discussed. The clique function \[ f = \bigvee_{C \in {[n] \choose m}} \bigwedge_{E \in {C \choose 2}} E \] detects if a given graph includes an \( m \)-vertex set with every possible edge filled, called \( m \)-clique. The graph has \( n \) vertices \( 1, 2, \ldots, n \) in \( [n] \), and some edges \( (x, y) \in [n] \times [n] \).
To be precise, edges can be undirected in \( G \) so the set of all possible edges can be \( {[n] \choose 2} \), called the edge space, rather than \( [ n] \times [n] \), whereas the vertex space \( [n] \) collects all the possible vertices. A Boolean circuit \( B \) to compute \( f \) is informed of a given \( G \) through the truth values of \( (x, y) \): each \( (x, y) \) regarded as a logical variable is set 1 if the edge exists in \(G \) and 0 otherwise.
In this setting, every node \( \alpha \) of \( B \) is assigned to a family \( {\mathcal E} \subset 2^{{[n] \choose 2} } \) of edge sets, each of which sets \( \alpha \) to be true. Assuming \( m= \sqrt[4] n \) and \( {\mathcal E} \) comprises \( p \)-edge sets where \( p = n^{19/20} \big/ 16 \), let’s consider the following problem.
What makes this problem interesting is that we’re trying to detect an \( m \)-clique in a given \( G \). If there is, any \( r \)-split \( \boldsymbol{X} \) must have an \( X_i \) containing an \( m/r \)-clique. So \(G \supset S\) includes at least \( m/r \) vertices in some \(X_i \), each connected to \( m/r -1 \) other vertices. Condition\((S, X_i ) \) inhibits this implying \( S \) contains no \( m/r \)-clique in \( X_i \). As a result, if we can always find such an \( \boldsymbol{X} \), it could lead to a way to reduce the clique detection problem to a smaller subproblem.
And our answer to the question is yes, by the same proof technique as Theorem 5. The key point is to convert each \( S \in \mathcal{E} \) into a vertex set \( U \) such that every \( x \in U \) is connected to at least \( m/(2r) \) other vertices in \(S \). In other words:
Then \( |U| \le m/4 \) because \( |S|=p= m^2 / (16r) \). Add any extra vertices to \( T \) to make \( |T| \) exactly \( m/4 \). (This is just to make \(U \) an \( m/4 \)-set not disturbing the construction.)
Now let \( \mathcal{F} \) be the family of such \(U \in {X \choose m/4} \), so we can use the same method as Theorem 5. The only difference comes from more than one \( S \in \mathcal{E} \) possibly mapped to a single \( U \in \mathcal{F} \). But it gives us no problem, because we can just allow multiplicity in \( \mathcal{F} \) so the sparsity could be negative. It can be checked on 5/13/24 and 7/22/24 that the same arguments work anywhere with multiplicity and negative sparsity of \( \mathcal{F} \).
Consequently, by this variation of Theorem 5, there exist an \( \boldsymbol{X} \) and a vast majority \( \mathcal{F}’ \subset \mathcal{F} \) such that \( |U \cap X_i| < m / (2r) \) for every \( U \in \mathcal{F}’ \) and \( X_i \).
This mean that for almost every \( S \), its subset \( S \cap {X_i \choose 2} \) includes no \( m/r \)-clique for any \( X_i \): we can view \( U \) as a label of \(S \) to list possible members of an \( m/r\)-clique in any \( X_i \). As there are less than \( m/(2r) \) such vertices in \( U \cap X_i \), there’s no way \( S \cap {X_i \choose 2} \) can include an \( m/r \)-clique.
This could provide a good platform to show the difficulty of computing cliques by a small enough Boolean circuit \(B \). We’ll detail this technique later when we discuss the computational complexity of the clique function.
Links for mobile devices
We’re in the middle of the induction step \( \Psi(j-1) \Rightarrow \Psi(j) \) to prove Theorem 6, having finished growing the first core \( C_1 \) of \( {\mathcal F}_1 \). It satisfies the four conditions of \( \Pi(j) \) presented last time.
We have proven the induction step. The property \( \Psi(r) \) immediately implies Theorem 6, so we’ve completed its proof as well.
Let me pose one question we might want to ask here: we only assumed the \( \Gamma(b) \)-condition of \( {\mathcal F} \) when it’s given. Is it possible that the final \( {\mathcal F}_i \) with \( \Psi(r) \)-ii) as the only cardinality lower bound gets near-empty? The answer is no. Because the \( \Gamma(b) \)-condition means \( 1= |{\mathcal F}[T]| < b^{-m} |{\mathcal F}| \) for every \( T \in {\mathcal F} \), so \( |{\mathcal F}| > b^m \). With this and \( \Psi(r) \)-i), we can see the final \( {\mathcal F}_i \) is far from empty.
Links for mobile devices
With Theorem 5 proven last time, we can now present a general statement to resolve our initial core growth problem.
This surely offers a solution to the problem: by Proposition 3 on 11/13/23, we are given an \( {\mathcal F} \) with the \( \Gamma ( cm^{\epsilon + \frac{1}{2}} k \ln^2 k ) \) condition. The theorem provides the three objects we need to perform the rank-\(g\) construction on \(X_1 \) and other \(X_j \).
To prove it, use Theorem 5 to obtain an \( r \)-split \( \boldsymbol{X} \) and subfamily \({\mathcal F’} \). Then recursively confirm the following proposition by the simultaneous core growth.
The approximate equality is due to \( r \gg 1 \) \( \Rightarrow \) \( (1- r^{-1})^{-r} \simeq e \), simpler than (1) on 7/20/23 to see. Perform the updates \[ \textrm{(7)} \qquad C_i \leftarrow C_i \cup S, \qquad \textrm{and} \qquad {\mathcal F}_i \leftarrow {\mathcal F}’_i [S], \] for \( i=1 \). Then \( C_1 \) and \( {\mathcal F}_1 \) meet the four required conditions of \( \Psi(j) \).
We’ll continue this to finish the proof of Theorem 6 next time. Note \( \Psi(r) \) implies the theorem.
Links for mobile devices