Continue our induction step to Lemma 1.3 on p. 3 of Paper S5.

We want to apply the induction hypothesis (2.1) given last time to the first \( z \) subfamilies \( \mathcal{F}_i \) found by the algorithm there. There is a small problem in it: although \( \mathcal{F}_i \) are mutually disjoint, their \( l \)-extensions may not be. If we just sum up the lower limits on \( |Ext(\mathcal{F}_i, l)| \) from (2.1), there could be some \( l \)-sets counted multiple times to yield a false lower limit.

Link to: 6/16/25

Links for mobile devices

• Paper S5
• Index page

To start the induction step for our proof of Theorem 1.1, assume (1.1) given last time for \( m-1 \).

Links to: 6/9/25, 5/5/25

Links for mobile devices

• Paper S5
• Index page

We start proving Theorem 1.1 of Paper S5 on the left.

Link to 7/8/24.

We’ll start its induction step next time.

Links for mobile devices

• Paper S5
• Index page

In this topic of the new chapter, we’ll discuss the two theorems of Paper S5 on extensions and shadows of \( \mathcal{F} \). We mainly look into the proof of:

Theorem 1.1. For any nonempty \( \mathcal{F} \subset {X \choose m} \) and \( l \in [n] – [m] \), \[ |Ext(\mathcal{F}, l)| > {n \choose l} \left\{ 1 – m \exp \left[ – \frac{(l-m+1)|\mathcal{F}|}{8 m! {n \choose m}} \right] \right\}. \]

The result is good for a small \( m \) such as 2 and 3, implying that it’d remove a vast majority of the \( \sqrt n \)-cliques included in an \( n \)-clique if we just eliminate any \( n^{2-\epsilon} \) edges of it. As said on 5/5/25, there would be less than \( {n \choose \sqrt n} \exp \left( – \frac{1}{9} n^{\frac{1}{2}-\epsilon} \right) \) remaining ones after the edge elimination.

We can derive a similar fact on a 3-uniform hypergraph \( \mathcal{H} =(V, E) \) with \( m =3 \), where \( V \) is a set of \(n \) vertices and \( E \) that of hyperedges, i.e., vertex triples \( (v_1, v_2, v_3) \in V^3 \). In such an undirected hypergraph, edges are unordered triples so \( (v_1, v_2, v_3) \) is identified with \( ( v_1, v_3, v_2), \), \( (v_2, v_1, v_3) \), etc. It’s a graph-theoretic convention that is good for critical arguments.

So, \( \mathcal{H} \) is essentially the same as a family of 3-sets that can be put into our set theoretical framework by \( V= [n] \) and \( E \subset {[n] \choose 3} \). This way we can say Vertices \( 1, 2, . \), Hyperedges \( (i, j, k) \), etc., giving a fine notational convenience. We use \( V= [n] \) as the universal set \( X \) for our discussions on graphs because of this.

Think of the same scenario as before for \(m=3 \) and \( l = \sqrt n \), where \( \mathcal{F} \subset {[n] \choose 3} \) is the set of \( n^{3-\epsilon} \) removed hyperedges. By the theorem, \[ |Ext(\mathcal{F}, l )| > {n \choose l} \left\{ 1 – 3 \exp \left[ – \frac{(l -2) n^{-\epsilon} }{8} \right] \right\} > {n \choose l} \left[ 1 – \exp \left( – \frac{1}{9} n^{\frac{1}{2}-\epsilon} \right) \right]. \] Each \( l \)-vertex set \( U \in Ext (\mathcal{F}, l) \) includes a hyperedge removed from the complete graph \( [n] \choose 3 \), so \( U \) can’t be an \( l \)-complete hypergraph. (For \( m >2\), an \( l \)-vertex set filled with every possible hyperedge is called complete hypergraph.) The theorem hence implies that removal of \( n^{3-\epsilon} \) hyperedges from an \(n \)-complete hypergraph results in the elimination of a vast majority of \( \sqrt n \)-complete hypergraphs.

So, the \(l \)-extension could really show some relationships between vertices, edges and hyperedges visibly. With this and other previous results such as the EGT, completement sparsity lemma, and the rank-\(g\)-construction, we can say we’ve seen some intrinsic nature of the combinatorial domain \( 2^X \) through the scope of \( Ext (\mathcal{F}, l) \).

We’ll start proving the theorem next time by induction on \( m \). Let’s get some idea about how the proof works for the crucial parameter \( m=2 \).

We first confirm the basis \( m=1 \) by seeing \[ |Ext(\mathcal{F}, l)| > {n \choose l} \left[ 1 – \exp \left( – \frac{l~|\mathcal{F}|}{8 n} \right) \right]. \] Put \( k = |\mathcal{F}| \) that is the number of the singleton sets in \( \mathcal{F} \subset {[n] \choose 1} \). Then the inequality is clear by the approximation \( {n – k \choose l} \simeq {n \choose l} \exp \left( – \frac{lk}{n} \right) \) we saw multiple times such as 7/20/23 and 8/11/23; it works because there are \( {n – k \choose l } \) sets \( U \in {[n] \choose l} \) each including none of the \( k \) sets.

Use this fact for \(m=2 \) toward \( |Ext(\mathcal{F}, l)| > {n \choose l} \left\{ 1 – 2 \exp \left[ – \frac{(l-1)|\mathcal{F}|}{8 n (n-1)} \right] \right\} \). Find some \( i \in [n] \) such that \( \mathcal{F} [i] \) is dense enough. ( The vertex \( i \in [n] \) here means a singleton set as well, so the expression \( \mathcal{F} [i] \) makes sense.) Consider pairs \( (i, U) \) such that \( U \in \mathcal{F} \) and \( i \in {U \choose 1} \). There are \( m | \mathcal{F}| \) of them so there must be an \( i_1 \in[n] \) such that \( |\mathcal{F}[i_1]| \ge m | \mathcal{F}| \big/ n \). Put \( \mathcal{F}_1 = \mathcal{F}[i_1] \) to remove it from \( \mathcal{F} \).

Continue this process to generate a number of mutually disjoint sufficiently large subfamilies \( \mathcal{F}_2, \mathcal{F}_3, \ldots, \). Apply the induction hypothesis to each \( \mathcal{F}_i \), then join them to prove the claim for \( m=2 \).

Links for mobile devices

• Paper S5
• Index page

Chapter 6, Topic 4. Limit of extension generators. Related to the second open problem posed on 4/14/25, this topic deals with some combinations of \( l \), \( \lambda \) and \( \mathcal{F} \) for which we cannot guarantee the existence of an \( ( l, \lambda) \)-extension generator of \( \mathcal{F} \). As its introduction, we’ll first remark that you cannot always find an \( (m+ m^{\epsilon}, c) \)-extension generator of an \( \mathcal{F} \subset {X \choose m} \) if \( \kappa (\mathcal{F}) > c m^\epsilon \ln n \) for some constant \( c \). We’ll show it by creating a counter example.

Here’s the main theorem we’ll prove there.

Theorem. Let a family \( \mathcal{F} \subset {X \choose m} \) generate \( \mathcal{G} \subset {X \choose k} \) for some \( k \in [n] – [m] \) such that \( \kappa( \mathcal{G} ) \ge \ln^2 n \), that is, \( \mathcal{G} \subset Ext( \mathcal{F}, k) \). The statement that there exists a \( (k-1, c \ln^2 n) \)-extension generator of such an \( \mathcal{F} \) is false.

We’ll confirm it through the circuit complexity of the \( k \)-counting problem represented by this Boolean function: \[ \bigvee_{C \in {[n] \choose k}} \bigwedge_{V \in {C \choose 1}} V. \] Like the clique function given on 1/27/2023, we can see that it is true if and only if the universal set \( [n] \) includes \( k \) or more existing vertices \( V \). In other words, the problem counts the vertices placed in \( [n] \) to return True if there are \( k \) of them. Among all the well-known monotone set/graph problems, the counting problem is a rare one that can be computed by a monotone Boolean circuit of polynomial size. We’ll figure this out in Topic 1 of Chapter 6.

Falsely assuming that such an \( \mathcal{F} \) always has a \( (k-1, c \ln^2 n) \)-extension generator, we’ll be able to make a similar construction to Paper 4 as we do for the clique problem in Topic 3. Then it would prove that there is no monotone Boolean circuit of polynomial size to compute the counting function. Since we know it cannot be true, it’ll prove the theorem.

This doesn’t just show the limit of extension generators, but also the difficulty of proving super-polynomial circuit complexity of the clique problem by a straightforward use of the EGT. We’ll discuss it as a possible leverage for further development into the next level.

Chapter 7. Hamming distance between two families of \( m \)-sets. We’ll show:

Theorem. The Hamming distance between two uniform families \( \mathcal{F}, \mathcal{G} \subset {X \choose m} \), defined to be \( \min_{U \in \mathcal{F},~V \in \mathcal{G}} ~2 |U – V| \), is \( O \left( m \big/ \ln m \right) \) if \( \max [\kappa(\mathcal{F}),~\kappa(\mathcal{G})] = O ( m^{1-\epsilon}) \).

Although I need more careful confirmation, I think the distance \(O \left( m \ln^{-c \ln \ln m} m \right) \) is likely provable.

This topic was the first one I started in this research. Seeing some potential in the relationship between the circuit complexity and combinatorics, I was wondering if it could be useful to develop tools around there. Because of the difficulty mentioned above, it didn’t work out exactly as expected for the P vs. NP problem. However, the above result and its proof arguments are interesting deserving to make a chapter of this study.

In addition to the topics presented so far, we’ll discuss the second version of Paper 1 when it’s uploaded. I’m hoping it could be done soon.

Links for mobile devices

• Paper 2 Ver. 2
• Paper S5
• Index page

Continued to present upcoming topics.

Chapter 5, Topic 2. On the disjointness between sets. We’ve been mainly working on families generated by set inclusion so far such as \( \mathcal{F}[S] \), \( Ext (\mathcal{F}, l) \) and \( Shd (\mathcal{F}, r) \). In this topic, we’re given \( k \) mutually disjoint \( m\)-sets \( U_1, U_2, \ldots, U_k \) to count \( l \)-sets each disjoint with at least one \( U_i \). By this we consider sets generated by disjointness, which possibly helps our later topics on circuit complexity.

We’ll derive that there are more than \( {n \choose l} \left[ 1 – \left( \frac{klm}{n} \right)^{k/2} \right] \) such \( l \)-sets if \( n \) is sufficiently larger than \( klm \). The complement sparsity of the \( l \)-sets is at least \( 2^{-1} k \ln \frac{n}{klm} \). So, any family \( \mathcal{F} \subset {X \choose l} \) with sparsity \( O ( k n^{-\epsilon} ) \) contains a vast majority each disjoint with some \( U_i \). We can use our \( k \)-disjoint-set claim to generalize this property.

Chapter 6, Topic 1. Circuit complexity and the P vs. NP Problem. Continued from the two of the earliest posts 1/21/23 and 1/27/23, we’ll define a combinatorial problem of rank \( r \) on \( {[n] \choose r} \), Boolean circuits to compute it, and the circuit complexity of the problem. We’ll do it in a framework consistent with our study so far, by which we’ll clarify the P vs. NP problem and its difficulty to solve it.

For a reason, this study focuses on monotone problems whose equivalent Boolean functions include no logical negations such as the clique function explained on 1/27/23 for the clique problem. Especially, we’ll delve into the nature of monotone graph problems that have rank 2 defined in the edge space \( {[n] \choose 2} \) as introduced by 8/12/2024. We see some of their examples with Boolean circuits to compute them. There we won’t convert a Turing machine into a Boolean circuit by the generic reduction algorithm but develop a way to code an algorithm to compute the problem directly into a circuit. This will help our investigation later.

Chapter 6, Topic 2. Standard methods for monotone circuit complexity. It’s well-known in computer science that any Boolean circuit computing the clique function without a logical negation has to have exponentially many nodes. It means the computation is no efficient practically impossible in a reasonable number of computational steps. To express this fact, we say the clique problem has exponential monotone circuit complexity.

We’ll demonstrate its standard proof using sunflowers. In Topic 1, we’ll see it could take many logical negations to even compute a very simple monotone problem. So, this result just gets us to the start point of investigating the P vs. NP problem, but it’d be a nice entrance door where we can imagine some ways to extend the method.

Chapter 6, Topic 3. Application of the EGT to circuit complexity. Paper 4 on the left proves the same exponential monotone circuit complexity with the EGT. We’ll cover it in this topic detailing the extra notes of 2/23/23. Because the proof is done in our set theoretical framework, we’ll be able to use all the tools we developed so far. I’m hoping that we can find some good ways for further advancement. I’m pretty sure our discussions will be exciting at least!

Links for mobile devices

• Paper 2 Ver. 2
• Paper S5
• Index page

I’ve uploaded the second version of Paper 2 on arXiv last week. The links to Paper 2 on the left and below now point to the latest one. It verifies all the tools necessary to prove the \( k\)- disjoint-set claim as we covered in the current and last chapters.

Also, another supplementary paper S5 is newly posted on the left. It proves two theorems on extensions and shadows of \( \mathcal{F} \subset {X \choose m} \) that’ll be covered by the next chapter. In this and next couple of posts, we’ll overview our subsequent topics including the two theorems. Those will clarify the direction this blog series should move forward to.

Chapter 5, Topic 1. Extensions and Shadows. (Chapter and topic numbers are tentative because another topic such as a fix of the Paper 1 error could interrupt the sequence.)

The first theorem of Paper S5 states \[ \textbf{Theorem 1.1.} \qquad \quad |Ext(\mathcal{F}, l)| > {n \choose l} \left\{ 1 – m \exp \left[ – \frac{(l-m+1)|\mathcal{F}|}{8 m! {n \choose m}} \right] \right\}, \] shown on the first page. It is true for any nonempty \( \mathcal{F} \subset {X \choose m} \) and \( l \in [n] – [m] \).

Unlike the EGT, this lower limit is good for a small \( m \) such as 2, and relatively large cardinalities such as \( | \mathcal{F}| = n^{2 – \epsilon} \). It implies the following interesting property: let a graph \( G \) have \( n \) vertices and all \( {n \choose 2} \) edges. Such a \( G \) is called \( n \)-clique as on 1/27/2023. Remove any \( n^{2-\epsilon} \) edges from \(G \), and a vast majority of \( \sqrt n \)-cliques are gone in the remaining graph of \( {n \choose 2} -n^{2-\epsilon} \) edges.

To see this, let \( X = \{ 1, 2, \ldots, n \} = [n] \) be the vertex set of \(G \), and \( \mathcal{F} \subset {[n] \choose 2} \) be the set of removed edges, so \( |\mathcal{F}| = n^{2-\epsilon} \). By Theorem 1.1, \[ |Ext(\mathcal{F}, l )| > {n \choose l} \left\{ 1 – 2 \exp \left[ – \frac{(l -1) n^{-\epsilon} }{8} \right] \right\} > {n \choose l} \left[ 1 – \exp \left( – \frac{1}{9} n^{\frac{1}{2}-\epsilon} \right) \right]. \] Here \( l= \sqrt n \gg 1 \) so \( Ext(\mathcal{F}, l) \) is the family of \( \sqrt n \)-vertex sets \( C \), each including a removed edge in \( \mathcal{F} \) impossible to be a \( \sqrt n \)-clique. Consequently, more than \( {n \choose \sqrt n} \left[ 1 – \exp \left( – \frac{1}{9} n^{\frac{1}{2}-\epsilon} \right) \right] \) such cliques will be destroyed if just any \( n^{2 – \epsilon } \) edges are taken away from an \( n \)-clique!

The second theorem of Paper S5 is about the sparsity of the \( r \)-shadow of \( \mathcal{F} \). We’ll show \[ \textbf{Theorem 2.1.} \qquad \quad \kappa[Shd (\mathcal{F}, r) ] < \frac{r}{m} \kappa(\mathcal{F}) + \frac{m^2}{n} + \ln^2 m, \] if both \( n/m \) and \( |\mathcal{F}| \) are sufficiently large. This means the sparsity \( \kappa[Shd (\mathcal{F}, r) ] \) is approximately less than \( \frac{r}{m} \kappa (\mathcal{F} ) \) under a weak assumption as said on 1/23/2023.

Links for mobile devices

• Paper 2 Ver. 2
• Paper S5
• Index page

We present two open problems in this post. The first question that could come to mind after our latest discussions is whether the \( b = m^{\frac{1}{2}+ \epsilon} \) parameter of the \( \Gamma \)-condition of the three-disjoint-set claim can be significantly reduced. What is the asymptotic minimum of \( b \) such that \( \Gamma(b) \) of \( \mathcal{F} \) \( \Rightarrow \) three mutually disjoint sets in \( \mathcal{F} \)?

Considering the overhead factor \( O \left( 8^{\sqrt{m}} k \log k \right) \) we dealt with in our proof of the \( k \)-disjoint-set claim, we can refine this problem into the following statement.

Open Problem 1: identify the smallest number \( \alpha  \ge 0 \) such that an \( \mathcal{F} \subset {X \choose m} \) satisfying the \( \Gamma( m^{\alpha + \epsilon} ) \)-condition for any \( \epsilon \in (0,1) \) and \( m \in \mathbb{Z}_{>0}  \) sufficiently larger than \( 1/\epsilon \) includes three mutually disjoint sets.

We’ve proven \( \alpha \le 1/2 \) as the three-disjoint-set claim. I conjecture \( \alpha >0 \), because in my attempts to prove the sunflower conjecture, it’s been hard to come up with a possibly working argument without growing a common core. In other words, it seems difficult to find a 3-sunflower with an empty core in an \( \mathcal{F} \) satisfying the \( \Gamma(c) \)-condition with a large constant \( c \). This leads to my feeling that the \( \Gamma( m^\epsilon) \)-condition does not necessarily mean three mutually disjoint sets in \( \mathcal{F} \). If \( \alpha \) is positive, it’d be interesting to find the minimum value of \( \alpha \) or its limit.

The second problem is about improving the EGT. Given a sufficiently small \( \epsilon \) and large \( m \):

Open Problem 2: find the minimum \( \beta >0 \) or its limit such that the following property holds true. For every \( l \in [n] – [m] \) and \( \lambda \in \left( 1, \frac{l}{m^{2-\beta}} \right) \),  there exists an \( (l, \lambda) \)-extension generator of any nonempty \( \mathcal{F} \subset {X \choose m} \) such that \[ |T| \le \frac{(1-\epsilon) \kappa (\mathcal{F})}{\ln \frac{l}{m^{2- \beta} \lambda} }.  \]

The EGT states almost the same except for the RHS replaced by \( \kappa (\mathcal{F}) \Bigr/ \ln \frac{\epsilon l}{m^{2} \lambda} \). We remark here that its truth for \( \beta = 1 \) means the sunflower conjecture for three petals, i.e., the case \( k=3 \) of the conjecture: given an \( \mathcal{F} \) with \( |\mathcal{F}|  > c^m \), its sparsity is \[ \kappa (\mathcal{F})  = \ln {n \choose m} – \ln |\mathcal{F} | < m \ln \frac{e n}{c m}, \] by \( {n \choose m} < \left( \frac{e n}{m} \right)^m \) shown on p. 23 of Paper 3. 

Choose \( l = \epsilon n \) and \( \lambda  = 1 / \epsilon \), and it is not difficult to see the statement implies \( |T| < m \) from \( n=|X| \le m |{\mathcal F}| = m c^m \) without loss of generality. With \( T \) being its \( ( \epsilon n,~ 1/\epsilon ) \)-extension generator, such an \( \mathcal{F} \) has to include a 3-sunflower, seen just like Step 4 of the proof of our 3-disjoint-set claim on 12/2/2024.

The case \( \beta = 1 \) of the statement is stronger than the existence of a 3-sunflower in \( \mathcal{F} \), so the question would remain open even if the three-petal sunflower conjecture were proven alone.

Consequently, it’s been my long-time question if it holds for a positive \( \beta \). We also note that we’ll later show an interesting negative result related to Problem 2.

Links for mobile devices

• Paper 3
• Index page

We proved the \( k \)-disjoint-set claim last time modifying its more constrained version previously proven. Noticing that the obtained two results don’t imply each other exactly, we see they can be combined into a single theorem.

Theorem on \( k \) elementwise disjoint subfamilies. There exist \( c \in \mathbb{R}_{>0} \) such that the following statement holds for any given \( k \in \mathbb{Z}_{\ge 3} \), and \( m \in \mathbb{Z}_{>0} \) sufficiently larger than \( k \), with \[ b= c 2^{\frac{5}{2} \sqrt{\lg m}} \sqrt{m \lg^2 m}~ k \lg k:  \] A family \( \mathcal{F} \subset {X \choose m} \) satisfying the \( \Gamma(b)\)-condition contains \(k \) elementwise disjoint subfamilies \( \mathcal{F}_i  \) such that \[ \textrm{(1.1)} \qquad |\mathcal{F}_i| > b^{-\epsilon m} \left(  \frac{\epsilon}{k \lg k} \right)^m |\mathcal{F} |, \quad \textrm{for every}~  i \in [k], \quad \textrm{where}~ \epsilon = \frac{1}{\lg c}. \]

Our proof of the two \( k \)-disjoint-set claims implies this. Suppose \( \mathcal{F} \) satisfies (2.2): \( |\mathcal{F} | > (cb k \lg k)^m \) given by the weak \( k\)-disjoint-set claim on 1/6/2025. Then \[ |\mathcal{F}| > b^{\frac{2m}{c}} \left( \frac{\epsilon^3}{k \lg k} \right)^m |\mathcal{F}|, \] as seen last time from \( \Pi_k (r) \). Regarding \( c \) as a large constant independent of the other variables, we can increase it to meet (1.1)  where \( \epsilon \) is \( \lg^{-1} c \) there. (It’s straightforward to check this from the current setting of the weak \( k \)-disjoint set claim.) So the theorem holds if (2.2).

Fixing \( c \) and \( \epsilon \) at the right constants, we can say the same for any \( \mathcal{F} \) such that \[ \textrm{(1.2)} \qquad |\mathcal{F}| \ge b^{\epsilon m} \left( \frac{k \lg k}{\epsilon} \right)^m, \] because our proof of \( \Pi_k (j) \) doesn’t rigorously use the lower bound value on \( |\mathcal{F}| \); we figured this out last time.

If \( \neg \)(1.2), the original claim guarantees \( k \) mutually disjoint sets in \( \mathcal{F} \) by its \( \Gamma(b) \)-condition. So, there are nonempty subfamilies \( \mathcal{F}_i \) such that (1.1), which correctly means just \( | \mathcal{F}_i| >0 \). Therefore, (1.1) holds for any \( \mathcal{F} \) considered by the theorem.

The confirmed statement makes a milestone of this blog series. Its proof uses almost all the knowledge we saw in Chapters 3 and 4 so far to show a simple proposition. The construction is interesting, proven to work as a tool set for some claims on extremal sets. (In combinatorics, “extremal sets” mean a collection of sets meeting some critical conditions.) This is our first concluding remark of this chapter.

We’ll pose two open problems next time.

Links for mobile devices

• Paper 3
• Index page

With the weak \(k\)-disjoint-set claim proven last time, it now remains to remove the second condition (2.2) on 1/6/25 to confirm the \( k \)-disjoint-set claim we initially presented.

Link to the 1/20/25 post.

In the next couple of posts, we’ll note some concluding remarks and subsequent topic plan before we move to the new chapter.

Links for mobile devices

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