We now show Theorem 2.3: \( \kappa[Shd(\mathcal{F}, r)] < \frac{4 r}{m} \kappa(\mathcal{F}) + \frac{m^2}{n} \) for any \( m \in [\epsilon n] \) and \( r \in [m] \) as said on p.6 of Paper S5.
Like we saw on 7/21/25, the theorem means that the \( r \)-shadow is a vast majority of \( {X \choose r} \) for many common combinations of \( n \), \( m \), \(r \) and \( \kappa(\mathcal{F}) \). In our past work, it had been crucial if the considered family is a majority of all such as the EGT, the rank-\(g \) construction for the \( k \)-disjoint-set claim, and Theorem 1.1. This has added another similar fact concluding the subchapter on extensions and shadows.
I’m now checking a new paper related to a fix of Paper 1. I’ll publish it in a few weeks before the next post is up.
With the double inequality (1.1) on 7/21/25 now available, let’s prove Theorem 2.1: \( \kappa[ Shd (\mathcal{F}, r) ] < \frac{r}{m} \kappa(\mathcal{F}) + \frac{m^2}{n} \) for powers \( m, r \) of 2 in this post. We first confirm it when \( r=m/2 \). It’s a case to pivot all other \( r \) as in our proof preview on 7/28/25.
Next time, we’ll show Theorem 2.3 to conclude the subchapter
To continue our proof of Lemma A.4 and Corollary A.5, we see the integral given in (3.3) last time equals \[ \int_0^y g(\alpha) d \alpha = \int_0^y \left( 1 – \frac{t \alpha}{y} \right)^{-k} d \alpha = y \int_0^1 \left( 1 – t \beta \right)^{-k} d \beta, \] by changing \( \alpha \) into \( \beta = \alpha / y \).
Continuing our proof of Lemma A.4 and Corollary A.5 of Paper S5.
It’s straightforward to check that \( g(\alpha) \) monotonically increases in \( \alpha \) strictly. The last line holds because \( g(0)=1 \) and \( g(y)=(1-t)^{-k} \). Thus, \[ (3.3) \qquad \int_0^y g(\alpha) d\alpha + 1 – \left( 1-t \right)^{-k} < U_k < \int_0^y g(\alpha) d\alpha, \] where the error \( 1 – (1-t)^{-k} \) is negative. We’ll use this approximation of \( U_k \) to continue the proof next time.
The Taylor series we use above is based on the well-known theorem given in standard textbooks:
Theorem on Taylor Series. If \( f: [a,x] \rightarrow \mathbb{R} \) has \( k+1 \) derivatives, \[ f(x) = f(a) + (x-a) \frac{f'(a)}{1!} + (x-a)^2 \frac{f”(a)}{2!} + \cdots + (x-a)^k \frac{f^{(k)}(a) }{k!} + (x-a)^{k+1} \frac{f^{(k+1)}(\xi) }{(k+1)!}, \] for some \( \xi \in [a, x]. \)
The formula can be called Taylor expansion of order \(k \) at \( a \), where \( (x-a)^{k+1} \frac{f^{(k+1)}(\xi) }{(k+1)!} \) is the error. So (3.2) above is actually an order-\( 0\) approximation. We however said the result of Corollary A.8 has first order because its error is bounded by \( yz/x \) times \( s+t \), a linear function of \(s \) and \( t \).
We referred to the approximation \( {x – z \choose y} \simeq {x \choose y} e^{-\frac{yz}{x} } \) once again to overview our proof of \( \kappa [Shd(\mathcal{F}, r)] \stackrel{<}{\sim} \frac{r}{m} \kappa(\mathcal{F}) \) last time. So far, we’ve used the asymptotic equality for these other purposes:
To devise a good upper bound on \( \kappa [Ext(\mathcal{F}, l)] \) to discuss the limit of the complement sparsity lemma on 7/20/23.
Remark A) of 9/9/23 for Lemma 1.2 of Paper S3 in order to show the EGT through the double mark lemma.
The next topic on the disjointness between sets will use it as a proof foundation, so all the three topics in the current chapter rely on the approximation. We didn’t particularly choose its applications, so it’s naturally very useful in this study.
We now start proving the double inequality (1.1) given on 7/21/25 as a more definitive formulation of the approximation. It’s equivalent to the corollary on p. 8 of Paper S5:
Corollary A.5. For any \( x, y, z \in \mathbb{Z}_{>0} \), \[ \max(y, z) < \epsilon x, \qquad \Rightarrow \qquad 0< \ln \frac{{x \choose y}}{{x-z \choose y}} – \frac{yz}{x} < \frac{yz(y+z)}{x^2}. \]
This is a first-order approximation of \( \ln \frac{{x \choose y}}{{x-z \choose y}} \) to \( \frac{yz}{x} \) with an error at most \( \frac{yz}{x} (t + s)\) where \( t= y/x \) and \( s= z/x \) are both smaller than any constant. We’ll find its higher-order version when we encounter a new need.
The approximate inequality \( \kappa [Shd(\mathcal{F}, r)] \stackrel{<}{\sim} \frac{r}{m} \kappa(\mathcal{F}) \) we presented last time is true as long as \( m \) and \( r \) are powers of 2 sufficiently smaller than \( n\). Surprisingly, both sides are asymptotically equal even in an extreme situation such as the following: suppose \[ 1 \ll r \ll \sqrt{m} \ll \sqrt[4]{n}, \] and \( \mathcal{F} \) consists of just one \( m \)-set. With the familiar Lemma 1.1 on p.9 of Paper S3, it’s straightforward to check that:
The sparsity of \( \mathcal{F} \) is \( \ln {n \choose m} \simeq m \ln \frac{n}{m} + m – \ln \sqrt{2m \pi} \)
That of \( Shd(\mathcal{F}, r) \) is \( \ln {n \choose r} – \ln {m \choose r} \simeq r \ln \frac{n}{m} \)
So \( \frac{r}{m} \kappa(\mathcal{F}) \simeq r \ln \frac{n}{m} + r \simeq \kappa [Shd(\mathcal{F}, r)], \) since \( \ln \frac{n}{m} \gg 1\).
In this situation where \( \kappa(\mathcal{F}) \) is the largest, we’re inclined to imagine a large sparsity gap between \( \mathcal{F} \) and \( Shd(\mathcal{F}, r) \), but the two values in the third note are close. It’s a good question whether \( \kappa [Shd(\mathcal{F}, r)] \simeq \frac{r}{m} \kappa(\mathcal{F}) \) holds in a number of common cases.
Here’s our proof sketch for the approximate upper limit \( \frac{r}{m} \kappa(\mathcal{F}) \) when \( r = m/2 \). Visualize the first moment \( \sum_{S \in {X \choose r}} |\mathcal{F}[S]| \) in a figure.
The lower half of the figure lists all the \( r\)-sets \( S \in Shd(\mathcal{F}, r) \), while the upper half shows each \( \mathcal{F}[S] \) and their elements \(V \in \mathcal{F}[S] \). As 6/22/23, the first moment counts the pairs \( (S, V) \), so \[ \#(S, V)= \sum_{S \in {X \choose r}} |\mathcal{F}[S]| = {n \choose m}{m \choose r} e^{-\kappa(\mathcal{F})} = {n \choose r}{n-r \choose r} e^{-\kappa(\mathcal{F})}. \]
Our observation here is that each \( \mathcal{F}[S] \) projected onto \( X – S \) is included in \( Shd(\mathcal{F}, r) \), i.e., \[ Shd (\mathcal{F}[S],r) \cap {X-S \choose r} \subset Shd(\mathcal{F},r).\] So, \( \#(S, V) \) is no more than \[ |Shd(\mathcal{F}, r)|^2 = {n \choose r}^2 e^{-2\kappa’} \simeq {n \choose r} {n-r \choose r} \exp \left( -2\kappa’ + \frac{r^2}{n} \right), \] \[ \textrm{where} \qquad \kappa’ = \kappa [Shd(\mathcal{F}, r)], \quad \textrm{and} \quad {n-r \choose r} \simeq {n \choose r} \exp\left( – \frac{r^2}{n} \right). \] Hence, \[ -\kappa(\mathcal{F}) \stackrel{<}{\sim} -2 \kappa’ + \frac{r^2}{n}, \qquad \Rightarrow \qquad \kappa’ \stackrel{<}{\sim} \frac{1}{2} \kappa (\mathcal{F}) + \frac{m^2}{n}, \] achieving our goal for \( r= m/2. \)
If \( r< m/2 \), apply the induction hypothesis to \( Shd (\mathcal{F}, m/2) \) to derive \( \kappa’ \stackrel{<}{\sim} \frac{r}{m} \kappa(\mathcal{F}) + \frac{m^2}{n} \) from the above fact for \( m/2 \).
We proved Theorem 1.1 by (1.1) on 6/16/25 last time, where we used the real sequence \( \{ c_m \} \) defined by (1.2) instead of the constant 8. As \( c_2=2 \) and \( c_3=4 \) are less than 8, we can slightly improve the upper limits on \( \sqrt n \)-complete graphs we saw on 5/5/25 and 6/9/25. We have two corollaries of (1.1) on p. 4 of Paper S5.
Corollary 1.5. A graph of \( n>1 \) vertices and \( {n \choose 2} – k \) edges contains no more than \[ 2 {n \choose l} \exp \left[ – \frac{(l-1)k}{2n (n-1)} \right] \] \( l \)-cliques.
Corollary 1.6. A 3-uniform hypergraph of \( n >2 \) vertices and \( {n \choose 3} – k \) hyperedges contains no more than \[ 3 {n \choose l} \exp \left[ \frac{(l-2)k}{4n (n-1)(n-2)} \right] \] complete hypergraphs of vertex size \(l \).
Their proof is just as discussed before: put the \( k \) removed edges (hyperedges) in \( \mathcal{F} \subset {[n] \choose m} \) for \( m=2 \) \( (m=3). \) Apply (1.1) to \( \mathcal{F} \) and we know that a vast majority of \( l \)-vertex sets each include a removed edge so they can’t be \(l \)-cliques/complete hypergraphs. The remaining ones amount to less than \[ 2 {n \choose l} \exp \left[ – \frac{(l-1)k}{2n (n-1)} \right]< {n \choose l} \exp \left( – \frac{1}{3} n^{\frac{1}{2}-\epsilon} \right), \] for \( m=2 \) and \( k= n^{2-\epsilon} \), and \[ 3 {n \choose l} \exp \left[ – \frac{(l-2)k}{4n (n-1)(n-2)} \right]< {n \choose l} \exp \left( – \frac{1}{5} n^{\frac{1}{2}-\epsilon} \right), \] for \( m=3 \) and \( k= n^{3-\epsilon} \). Those are slightly better values than before.
We’ve concluded our discussions on Theorem 1.1. We’ll start proving Theorems 2.1 and 2.3 on the sparsity of an \( r \)-shadow next time.
We’ll finish our proof of Theorem 1.1 of Paper S5 in this post. Our last task is to show (1.1) on 6/16/25, equivalently \( |Ext( \mathcal{F}, l) | > (1 – m e^{-\beta}) {n \choose l} \), from the inequality (3.4) we verified last time.
Comparing the two, we think if there is any link between \( { n \choose l} \) and \( \sum_{i=1}^z {n-i \choose l-1}. \) There is actually a well-known identity in combinatorics that connects the two. It’s called hockey-stick identity shown on Wikipedia, also present on the first page of Paper S3. It’s named so because its derivation in Pascal’s triangle looks like a hockey stick as the Wikipedia article says.
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.
