We look into the proof of EGT for a next while. As its first step, let’s see some properties of the sparsity of a uniform family \( {\mathcal F} \subset {X \choose m} \) that is $$ \kappa ({\mathcal F} ) = \ln {|X| \choose m} – \ln |{\mathcal F}|,$$ as given in the terminology page on the left and the 2/23 post. With this notation, we see the EGT to claim the existence of an \( (l, \lambda) \)-extension generator S of any \( {\mathcal F} \) such that \( |S| < \kappa ({\mathcal F}) \Big/ \ln \frac{\epsilon l}{\lambda m^2} \) if \( 1 < \lambda < \epsilon l / m^2 \). Also the split lemma (in the 3/3 post) claims the existence of an m-split \(\boldsymbol{X} \) such that \( \kappa \left[ {\mathcal F} \cap {\boldsymbol{X} \choose m} \right] < m \).
The sparsity is just another form of a cardinality measure, but it can be posed with its maximum number (i.e., \( |{\mathcal F}| = {n \choose m} e^{-\kappa({\mathcal F})} \) where n=|X| and e=2.71.. ), allowing for some algebraic manipulations. One of its simplest examples is to show \( \kappa [Ext ({\mathcal F}, l) ] \le \kappa ({\mathcal F}) \), meaning that the l-extension is at least as dense as \({\mathcal F} \).
Consider all pairs (U, Y) of m-sets \( U \in {\mathcal F} \) and l-sets Y such that \( U \subset Y\). There are exactly $$ |{\mathcal F}| {n-m \choose l-m} = {n \choose m} e^{-\kappa({\mathcal F})} {n-m \choose l-m}= {n \choose l} e^{-\kappa({\mathcal F})} {l \choose m} $$ such pairs, where the well-known identity \( {n \choose m}{n-m \choose l-m} = {n \choose l} {l \choose m} \) holds because the both sides equal \( \frac{n!}{m! (n-l)! (l-m)!} \). Each l-set Y can include at most \( {l \choose m} \) sets \( U \in {\mathcal F} \), so there must be \( {n \choose l} e^{-\kappa({\mathcal F})} \) or more \( Y \in Ext ({\mathcal F}, l) \). This proves \( \kappa [Ext ({\mathcal F}, l) ] \le \kappa ({\mathcal F}) \).
We can also see that the r-shadow \( Shd ({\mathcal F}, r ) \), the family of r-sets V each included in some \( U \in {\mathcal F} \), is at least as dense as \( {\mathcal F} \): the first moment of \( {\mathcal F} \) is defined to be $$ \sum_{V \in {X \choose r}} |{\mathcal F}[V]| = |{\mathcal F}|{ m \choose r} = {n \choose m} e^{-\kappa({\mathcal F})} {m \choose r} = {n \choose r} e^{-\kappa({\mathcal F})} {n-r \choose m-r}. $$ It is equal to the number of pairs (V, U) such that \( V \in {X \choose r} \) and \( V \subset U \in {\mathcal F} \), so there must be at least \( { n\choose r} e^{-\kappa({\mathcal F})} \) sets \( V \in Shd ({\mathcal F}, r) \), proving \( \kappa [Shd ({\mathcal F}, r) ] \le \kappa ({\mathcal F}) \).
This bound can be improved into \( \kappa [Shd ({\mathcal F}, r) ] \) roughly less than \( \frac{r}{m} \kappa ({\mathcal F}) \) under some simple conditions met, which we’ll see later in this blog. Also, Paper 3 on the left investigates some variations of the kth moment \( \sum_{V \in {X \choose r}} |{\mathcal F}[V]|^k \) to derive some interesting facts.
We’ll continue on this topic next time.
Links for mobile devices