We’re checking the truth of Theorem 2.1 on p. 4 of Paper S3 as the last step of this topic. Last time, we introduced the norm \( \left\| {\mathcal G} \right\| = \sum_{U \in {\mathcal G}} w(U) \) induced by a weight function \( w: 2^X \rightarrow {\mathbb R}_{\ge 0} \) to define the weighted sparsity \( \kappa ( {\mathcal G} ) = \ln {n \choose m} – \| {\mathcal G} \| \). With \( \left| {\mathcal F} \cap {Y \choose m} \right| \) replaced by \( \left\| {Y \choose m} \right \| \), and the other \( | \cdot | \) by \( \| \cdot \| \), all the proof steps we took for Corollary 3.2 work just as well. Other than Remark A) on p. 4, these hold true:
- Remark E) with the weighted \( \Gamma \)-condition (15) given last time.
- Proof of the double mark lemma with \( \| \cdot \| \).
- Lemma Lemma 2.3 with \( \| {\mathcal D} \| \) and \( \| {\mathcal M} \| \) as defined last time, and \( x_i = \left\| {Y_i \choose m} \right \| \).
They are all ok because the norm \( \| \cdot \| \) is linear with respect to \( {\mathcal F} \), i.e., it’s the sum of nonnegative weight \( w(U) \) considered for \( U \in {\mathcal F} \) only. With those, we’ve just finished checking everything in the current Paper S3.
As said in the 2nd paragraph last time, the EGT could be useful only if it supports weight, and we can state its weighted version proven by Theorem 4.1 and the complement sparsity lemma. Here is how it reads:
The Weighted EGT: let the universal set \( X \) be weighted by \( 2^X \rightarrow [0, 1] \) to induce the norm \( \| \cdot \| \), \( \epsilon \in {\mathbb R}_{>0} \) be a sufficiently small constant, $$ m \in [n], \quad l \in [n] – [m], \quad \textrm{and} \quad \lambda \in \left( 1,~\frac{\epsilon l}{m^2} \right). $$ For every \( {\mathcal F} \subset {X \choose m} \) with positive norm, there exists a set \( T \) with \( |T| \le \kappa({\mathcal F}) \Big/ \ln \frac{\epsilon l}{m^2 \lambda} \) such that there are \( \left( 1 – e^{-\lambda} \right) {n-|T| \choose l-|T|} \) sets \(Y \in {X \choose l}[T] \) each with \( \left\| {Y \choose m} \right\| \ge \left( \frac{\epsilon}{\lambda} \right)^{m-|T|} {l -|T| \choose m – |T|} \|{\mathcal F}[T] \| \Big/ {n-|T| \choose m-|T|}. \)
We first notice that it doesn’t make a practical difference, by the linearity of the norm, if we divide all \( w(U) \) by their maximum. After zeroing \( w(U) \) for \( U \not \in {\mathcal F} \), we have \( 0< w(U) \le 1 \) for \( U \in {\mathcal F} \) and \( w(U)=0 \) for \( U \not \in {\mathcal F} \) without loss of generality. That’s why the given weight is \( w: 2^X \rightarrow [0, 1] \) rather than \( 2^X \rightarrow {\mathbb R}_{\ge 0} \).
To prove the statement:
So, it suffices to prove:
Proposition: for every \( {\mathcal F} \subset {X \choose m} \) with positive norm, there exists a set \( T \) with \( |T| \le \kappa({\mathcal F}) \Big/ \ln \frac{\epsilon l}{m^2 \lambda} \) such that there are \( \left( 1 – e^{-\lambda} \right) {n-|T| \choose l-|T|} \) sets \(Y \in {X \choose l}[T] \) each with \( \left\| {Y \choose m} \right\| > ( 1 – \sqrt[12] \epsilon) {l_0 -|T| \choose m – |T|} \|{\mathcal F}[T] \| \Big/ {n-|T| \choose m-|T|}. \)
We just sketch its proof here. As the discussion goes on p. 9:
This T meets \( \| {\mathcal F} [T \cup S] \| < b^{-|S|} \| {\mathcal F} [T] \| \) for all nonempty sets \( S \subset X-T \): if there were an S violating it, the union \( T \cup S \) would make a larger \(T \).
Assume \( T=\emptyset \) to think of X instead of X-T for simplicity. Then \( {\mathcal F}= {\mathcal F} [T] \) satisfies the regular \( \Gamma(b) \)-condition with the norm \( \| \cdot \| \), so it meets (15). By Theorem 2.1, \( Ext ({\mathcal F}, l_0) \) includes \( ( 1 – 2\gamma^{-1/3} ) {n \choose l} \) sets \( Y_0 \in {X \choose l} \) each with \( \left| {Y_0 \choose m} \right\| > ( 1 – \gamma^{-1/3} ) {l_0 \choose m} \| {\mathcal F} \| \Big/ { n \choose m} \).
We further extend \( Ext ({\mathcal F}, l_0) \) into \( Ext ({\mathcal F}, l) \), whose complement sparsity is greater than \( \lambda \) by the general bound of the complement sparsity lemma. Hence, there are \( ( 1- e^{-\lambda}) {n \choose l} \) sets \( Y \in {X \choose l } \) with \( \left| {Y \choose l} \right\| > ( 1 – \gamma^{-1/3} ) {l_0 \choose m} \| {\mathcal F} \| \Big/ { n \choose m} \), finishing the proof of the proposition and the weighted EGT.
If you need the weighted EGT in another proof, you can just use Theorem 2.1 and the complement sparsity lemma in its argument. So I usually don’t write it explicitly.
By this we finish the current topic, but the next two will be still related to the EGT. We’ll explore things about the collective \( \Gamma \)-condition starting next time.
Links for mobile devices