With (6.1): \( \kappa(\mathcal{G} ) < \frac{1}{2} \kappa (\mathcal{F}) + \frac{m^2}{8n} \left(1 + \frac{m}{n} \right) + \frac{1}{2} \ln m_* \) shown last time for the pivoting case \( r= m_* \), we continue to prove Theorem 2.1 of Paper S5.
Prove it by induction on \( m \), whose base case \( m = 1 \) is simple to check. For induction step, assume true for all positive integers less than \( m \), and prove true for \( m \). If \( r <m_* \), the claim is shown by (6.1) as follows.
We now prove the theorem when \( r > m_* \) as previewed on 7/28/25.
We’ll apply the induction hypothesis to those \( \mathcal{F}[S] \) next time.
Links for mobile devices
With the double inequality (1.1) on 7/21/25 now available, let’s start proving Theorem 2.1: \( \kappa[ Shd (\mathcal{F}, r) ] < \frac{r}{m} \kappa(\mathcal{F}) + \frac{m^2}{n} + \ln^2 m \). 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.
Links for mobile devices
Let’s finish proving Corollary A.8 in this post to confirm the double inequality (1.1) on 7/21/25.
Links for mobile devices
To continue our proof of Lemma A.7 and Corollary A.8, 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 \).
Link to: 8/4/25.
Links for mobile devices
Continuing our proof of Lemma A.7 and Corollary A.8 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 \).
Links for mobile devices
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:
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. 10 of Paper S5:
Corollary A.8. 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 assumed smaller than any constant. We’ll find its higher-order version when we encounter a new need.
Links for mobile devices
The approximate inequality \( \kappa [Shd(\mathcal{F}, r)] \stackrel{<}{\sim} \frac{r}{m} \kappa(\mathcal{F}) \) we presented last time is true for many parameter combinations. 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:
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}) \). Assume \( m \) is a power of 2, and \( 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 said on 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) \), and if \( r> m/2 \), to all reasonably large \( \mathcal{F}[S] \) to argue similarly. We’ll see this proves \( \kappa [Shd(\mathcal{F}, r)] \stackrel{<}{\sim} \frac{r}{m} \kappa(\mathcal{F}) \) for every power \(m \) of 2 such that \( n \gg m^2 \), and \( r \le m \).
Links for mobile devices
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 Theorem 2.1 on the sparsity of an \( r \)-shadow next time.
Links for mobile devices
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.
Link to: 8/25/23
Links for mobile devices
