Last time, we saw the approximate upper bound (4) as the main observation to prove the double mark lemma. Please take a look at the first paragraph of p.6 of Paper S3 for which we are considering the unit norm \( \| \cdot \| \) that just means the cardinality for us now (except for \( \left\| {Y \choose m} \right\| \) meaning \( \left| {\mathcal F} \cap {Y \choose m} \right| \)). We see the claim is not too far from (4) despite it looks a bit lengthy.
It’s so because of this identity: $$ (6) \qquad {n \choose l}{l \choose m}^2 = {n \choose m} \sum_{j=0}^m {m \choose j} {n-m \choose m-j} {n-2m+j \choose l-2m+j}.$$ The both sides are equal because they count the number of double marks when \( {\mathcal F} = {X \choose m} \), i.e., all triples (U, V, Y) such that U and V are m-sets included in the l-set Y. The LHS counts Y first so the left factor is \( {n \choose l} \), for each of which there are \( {l \choose m}^2 \) pairs (U, V).
If you count U first, their number \( {n \choose m} \) makes the first factor as in the RHS. Then count their (m-j)-neighbors V such that |V-U| = m-j, whose number for each U is \( {m \choose j} {n-m \choose m-j} \). For each \( V \cup U \) of cardinality 2m-j, there are \( {n – 2m+j \choose l-2m + j }\) sets \( Y \in {X \choose l} \) including the union. Two (U, V, Y) of different j can never be the same, so it counts all (U, V, Y) each just once summing up the product for all possible j. This justifies the RHS of (6) proving they are equal.
Knowing that, please follow through the intuitive explanation below the proof on p. 6-7 of Paper S3. The first inequality is nothing but (4) we found last time. Use $$ {n-m \choose m-j} {n – 2m+j \choose l-2m+j} = {n-m \choose m-j} {n – m – (m-j) \choose l-m – (m-j)} = {n-m \choose l-m}{l-m \choose m-j },$$ true by the identity \( {x \choose z} {x-z \choose y-z} = {x \choose y}{y \choose z} \), to reach the bottom of p. 6.
Applying it to the RHS of (6), we also find that $$ {n \choose m} \sum_{j=0}^m {m \choose j} {n-m \choose m-j} {n-2m+j \choose l-2m+j} = {n \choose m} {n-m \choose l-m} \sum_{j=0}^m{l-m \choose m-j} {m \choose j}, $$ whose RHS can be seen to count (U, V, Y) in the order of U, Y then V.
By Vandermonde’s identity we used in the 7/26 post, \( \sum_{j=0}^m{l-m \choose m-j} {m \choose j} = {l \choose m} \), so the above is further transformed into $$ {n \choose m}{n-m \choose l-m}{l \choose m} = {n \choose l}{l \choose m}^2. $$ This is algebraic proof of the identity (6) with \( {x \choose z} {x-z \choose y-z} = {x \choose y}{y \choose z} \) used to count the set tuples in different component orders.
We now see the discussion is good in the first paragraph of p. 7, noting the approximate bound \( {l -m \choose m-j} {m \choose j} \stackrel{<}{\sim} {l \choose m} \left( \frac{m^2}{l} \right)^j \) from G) on p. 5 and also (2) in the 8/4 post. It is an adaptation of the algebraic proof of (6) to any \( {\mathcal F} \) satisfying \( \Gamma(b) \). As we pointed out last time for the collective \( \Gamma \)-condition, we just use \( {m \choose j} \le m^j \) here.
These justify the double mark lemma \( |{\mathcal D}| < \frac{e^{-2\kappa({\mathcal F}) }}{1- (2 \gamma)^{-1}} {n \choose l}{l \choose m}^2 \) if \( \Gamma(b) \) of \({\mathcal F} \) in an intuitively convincing way.
Links for mobile devices