Here’s our last remark on the \(r\)-split lemma we’ve been discussing in the last few posts.
Remark 4: the first proof step we found on 5/13/24 is useful for our initial core growth problem. We argued on 4/29/24 that we want an \( r \)-split \( {\boldsymbol X} \), \( k \) mutually disjoint sets \( C_i \) and subfamilies \( {\mathcal F}_i \subset {\mathcal F}[C_i] \) on \( {\boldsymbol X} \) satisfying necessary \( \Gamma \)-conditions to prove Proposition 3 on 11/13/23. To start its proof, we are just given an \( {\mathcal F} \) with \( \Gamma (b ) \) where \( b= c m^{\frac{1}{2} + \epsilon} k \ln^2 k \). To apply the rank \(g \)-construction, we want \( {\mathcal F} \) on a good split with a \( \Gamma \)-condition, but we can’t just use the split lemma or grow the core because we’re trying to find \( k \) mutually disjoint sets in \( {\mathcal F} \). The initial core growth problem asks how to construct such \( {\boldsymbol X} \), \( C_i \) and \( {\mathcal F}_i \).
Our solution to the problem finds pairs \( (U, X_1) \) of \( U \in {\mathcal F} \) and \( d\)-sets \(X_1 \) the same way as the 5/13/24 post, so there are \( {m \choose q} {n-m \choose d-q} |{\mathcal F}|\) of them such that \( |U \cap X_1|=q \). It means there are \( {m \choose q} {n-m \choose d-q} {n \choose d}^{-1} |{\mathcal F}|\) sets \( U \in {\mathcal F} \) with \( |U \cap X_1|= q \) for some \(X_1 \). Put them in \( {\mathcal F}_1 \) fixing the \(X_1 \).
We choose \( r= m^{\frac{1}{2} – \epsilon^2} \) as before, so \[ d = \frac{n}{r} = \frac{n}{m^{\frac{1}{2} – \epsilon^2} } , \qquad \textrm{and} \qquad q= \frac{m}{r} = m^{\frac{1}{2} + \epsilon^2}. \] Assume \( r \) divides both \( n \) and \( m \), and \( n \gg m^2 \) for simplicity here. We notice something similar to our finding on 5/27/24:
In other words, the sparsity increase \( \kappa ({\mathcal F}_1) – \kappa({\mathcal F }) \) is no more than \( \ln q + O(1) = O (\ln m) \). By this we can grow the core \( C_1=\emptyset \) for the first step: let \( b_1 \) be slightly smaller than \( b \), say \( b_1= (1 – \epsilon/r ) b \). Find a maximal set \( C_1 \) such that \[ |{\mathcal F}_1[C_1] | \ge b_1^{-|C_1|} |{\mathcal F}|. \] It’s not too hard to see \( |C_1| = O ( r \ln m ) \ll b \) by the given \( \Gamma(b) \)-condition of \( {\mathcal F} \). After it, \( {\mathcal F}_1[C_1] \) satisfies the \( \Gamma(b_1) \)-condition in \( X-C_1 \).
Because \( |C_1| \) is asymptotically smaller than \(b \), we can delete the whole \( {\mathcal F}[C_1] \) from \( {\mathcal F} \) without much disturbing its \(\Gamma(b) \)-condition, since it just reduces less than \( k^{-1} m^{-\epsilon} \) of \( {\mathcal F} \). We can similarly detect \( {\mathcal F}_2[C_2], {\mathcal F}_3[C_3], \ldots, {\mathcal F}_k[C_k] \) with the same \(X_1\), besides the \( {\mathcal F}_1[C_1] \) we just found. We will clarify more about this process of simultaneous core growth later.
The process can continue for \( X_2, X_3, \ldots, X_r \) like the induction steps for the \( r \)-split lemma on 5/20/24 to construct \( {\boldsymbol X} \), \( C_i \) and \( {\mathcal F}_i \) we need. In the next while, we will see its details to resolve the initial core growth problem eventually. Section 4.1 on p. 12-14 of Paper 3 deals with it in a bit different way. However, our arguments presented here will be its sequel improving the overall quality significantly. So, we’ll just focus on ours.
Links for mobile devices