Title: Daniel's Flashcards / Year 4 / Term 1 / Combinatorics

html: Definition 1 (Set system). Let X be a set. A set system on X (or a family of subsets of X) is a family A ⊂ P ( X ).
nothing: True

html: Definition 2 (Discrete cube). Make P ( X ) into a graph by joining A and B if | A Δ B | = 1, i.e. if A = B ∪ { i } for some i, or vice versa. We call this ths discrete cube Q n (if X = [ n ]).
nothing: True

html: Definition 3 (Chain). Say A ⊂ P ( X ) is a chain if ∀ ⁡ A , B ∈ A, either A ⊂ B or B ⊂ A.
nothing: True

html: Definition 4 (Antichain). Say A is an antichain if ∀ ⁡ A , B ∈ A, A ≠ B, we have A ⁄ ⊂ B.
nothing: True

html: Theorem 5 (Sperner’s Lemma). Assuming that:
- A ⊂ P ( X ) is an antichain
Then | A | ≤ n ⌊ n 2 ⌋.
proof: Proof. We’ll decompose P ( X ) into n 1 2 n chains – then done. To achieve this, it is sufficient to find:
- (i) For each r < n 2, a matching from X ( r ) to X ( r + 1 ) (recall that a matching here means a set of disjoint edges, one for each point in X ( r )).
- (ii) For each r ≥ n 2, a matching from X ( r ) to ( r − 1 ).
We then put these together to form our chains, each passing through X ( ⌊ n 2 ⌋ ).
By taking complements, it is enough to prove (i).
Let G be the (bipartite) subgraph of Q n spanned by X ( r ) ∪ X ( r + 1 ): we seek a matching from X ( r ) to X ( r + 1 ). For any S ⊂ X ( r ), the number of S − Γ ( S ) edges in G is | S | ( n − r ) (counting from below) and ≤ | Γ ( S ) | ( r + 1 ) (counting from above).
Hence, as r < n 2,
| Γ ( S ) | ≥ | S | ( n − r ) r + 1 ≥ | S | .
Thus by Hall’s Marriage theorem, there exists a matching. □
nothing: True

html: Definition 6 (Shadow). For A ⊂ X ( r ) (1 ≤ r ≤ n), the shadow of A is ∂ A = ∂ − A ⊂ X ( r − 1 ) defined by, ∂ A = { B ∈ X ( r − 1 ) : ∃ ⁡ A ∈ A , B ⊂ A }.
nothing: True

html: Proposition 7 (Local LYM). Assuming that:
- A ⊂ X ( r )
- 1 ≤ r ≤ n
Then
| ∂ A | n r − 1 ≥ | A | n r .
proof: Proof. The number of A − ∂ A edges in Q n is | A | r (counting from above) and is ≤ | ∂ A | ( n − r + 1 ) (counting from above). So
| ∂ A | | A | ≥ r n − r + 1 .
But n r − 1 n r = r n − r + 1, so done. □
nothing: True

html: Theorem 8 (LYM Inequality). Assuming that:
- A ⊂ P ( X ) is an antichain
Then
∑ r = 0 n | A ∩ X ( r ) | n r ≤ 1 .
proof: Proof 1. “Bubble down with Local LYM”.
Have | A n | n n ≤ 1. Now, ∂ A n and A n − 1 disjoint (as A is an antichain), so
| ∂ A n | n n − 1 + | A n − 1 | n n − 1 = | ∂ A n ∪ A n − 1 n n − 1 ≤ 1 ,
whence
| A n | n n + | A n − 1 | n n − 1 ≤ 1
by Local LYM.
Now, note ∂ ( ∂ A n ∪ A n − 1 ) is disjoint from A n − 2 (since A is an antichain), so
| ∂ ( ∂ A n ∪ A n − 1 ) | n n − 2 + | A n − 2 | n n − 2 ≤ 1 ,
whence
| ∂ A n ∪ A n − 1 | n n − 1 + | A n − 2 | n n − 2 .
(Local LYM) so
| A n | n n + | A n − 1 | n n − 1 + | A n − 2 | n n − 2 ≤ 1 .
Continue inductively. □
nothing: True

html: Definition 9 (i j-compression). Fix 1 ≤ i < j ≤ n. The i j-compression C i j is defined as follows:
For A ∈ X ( r ), set
C i j ( A ) = { A ∪ i − j if j ∈ A , i ∉ A A otherwise ,
and for A ⊂ X ( r ), set
C i j ( A ) = { C i j ( A ) : A ∈ A } ∪ { A ∈ A : C i j ( A ) ∈ A } .
nothing: True

html: Lemma 10. Assuming that:
- A ⊂ X ( r )
- 1 ≤ i < j ≤ n
Then | ∂ C i j ( A ) | ≤ | ∂ A |.
proof: Proof. Write A ′ for C i j ( A ). Let B ∈ ∂ A ′ − ∂ A. We’ll show that i ∈ B, j ∉ B and B ∪ j − i ∈ ∂ A − ∂ A ′. [Then done].
Have B ∪ x ∈ A ′ for some x, with B ∪ x ∉ A (as B ∉ ∂ A). So i ∈ B ∪ x, j ∉ B ∪ x, and ( B ∪ x ) ∪ j − i ∈ A.
Cannot have x = i, else ( B ∪ x ) ∪ j − i = B ∪ j, giving B ∈ ∂ A, contradiction.
Hence we have i ∈ B, j ∉ B.
Also, B ∪ j − i ∈ ∂ A, since ( B ∪ x ) ∪ j − i ∈ A.
Suppose B ∪ j − i ∈ ∂ A ′: so ( B ∪ j − i ) ∪ y ∈ A ′ for some y. Cannot have y = i, else B ∪ j ∈ A ′ – so B ∪ j ∈ A (as j ∈ B ∪ j), contradicting B ∉ ∂ A. Hence j ∈ ( B ∪ j − i ) ∪ y and i ∉ ( B ∪ j − i ) ∪ y.
Whence both ( B ∪ j − i ) ∪ y and B ∪ y belong to A (by definition of A ′), contradicting B ∉ ∂ A. □
cloze1: True

html: Definition 11 (Left-compressed). Say A ⊂ X ( r ) is left-compressed if C i j ( A ) = A for all i < j.
nothing: True

html: Definition 13 (U V-compression). Let U , V ⊂ X with | U | = | V |, U ∩ V = ∅ and max ⁡ V > max ⁡ U. We define the U V-compression as follows: for A ⊂ X,
C U V ( A ) = { A ∪ U − V if V ⊂ A , U ∩ A = ∅ A otherwise ,
and for A ⊂ X ( r ), set
C U V ( A ) = { C U V ( A ) : A ∈ A } ∪ { A ∈ A : C U V ∈ A } .
nothing: True

html: Lemma 14. Assuming that:
- A ⊂ X ( r ) is U V-compression for all U , V with | U | = | V |, U ∩ V = ∅, max ⁡ V > max ⁡ U
Then A is an initial segment of colexicographic.
proof: Proof. Suppose not. So there exists A , B ∈ X ( r ) with B < A, in colexicographic but A ∈ A, B ∉ A.
Put V = A ∖ B, U = B ∖ A.
Then | V | = | U |, and U , V disjoint, and max ⁡ V > max ⁡ U (since max ⁡ ( A Δ B ) ∈ A, by definition of colexicographic).
So C U V ( A ) = B, contradicting A is U V-compression. □
cloze1: True

html: Lemma 15. Assuming that:
- U , V ⊂ X
- | U | = | V |
- U ∩ V = ∅
- max ⁡ U < max ⁡ V
- A ⊂ X ( r )
- ∀ ⁡ u ∈ U ∃ ⁡ v ∈ V such that A is ( U − u , V − v ) -compressed (∗)
Then | ∂ C U V ( A ) | ≤ | ∂ A |.
proof: Proof. Let A ′ = C U V ( A ). For B ∈ ∂ A ′ − ∂ A, we’ll show U ⊂ B, V ∩ B = ∅, and B ∪ V − U ∈ ∂ A − ∂ A ′. (Then done).
Have B ∪ x ∈ A ′ for some x, and B ∪ x ∉ A, so U ⊂ B ∪ x, V ∩ ( B ∪ x ) = ∅, and ( B ∪ x ) ∪ V − U ∈ A (by definition of C U V).
If x ∈ U: there exists y ∈ U such that A is ( U − x , V − y )-compressed, so from ( B ∪ x ) ∪ V − U ∈ A we have B ∪ y ∈ A – contradicting B ∉ ∂ A, contradiction.
Thus x ∉ U, and so U ⊂ B, V ∩ B = ∅. Certainly B ∪ V − U ∈ ∂ A (because ( B ∪ x ) ∪ V − U ∈ A), so just need to show that B ∪ V − U ∉ ∂ A ′.
Suppose B ∪ V − U ∈ ∂ A ′: so ( B ∪ V − U ) ∪ w ∈ A ′, for some w. Also have ( B ∪ V − U ) ∪ w ∈ A (for example, as V contained in it).
If w ∈ U: know A is ( U − w , V − z )-compressed for some z ∈ V, so B ∪ z ∈ A – contradicting B ∉ ∂.
If w ∉ U: have V ⊂ ( B ∪ V − U ) ∪ w, U ∩ ( ( B ∪ V − U ) ∪ w ) = ∅, so by definition of C U V we must have that both ( B ∪ V − U ) ∪ w and B ∪ w ∈ A – contradicting B ∉ ∂ A, a contradiction. □
cloze1: True

html: Theorem 16 (Kruskal-Katona). Assuming that:
- A ⊂ X ( r ), 1 ≤ r ≤ n
- C is the initial segment of colexicographic on X ( r ) with | C | = | A |
Then | ∂ C | ≤ | ∂ A |. In particular: if | A | = k r, then | ∂ A | ≥ k r − 1.
proof: Proof. Let Γ = { ( U , V ) : | U | = | V | > 0 , U ∩ V = ∅ , max ⁡ U < max ⁡ V } ∪ { ( ∅ , ∅ ) }. Define a sequence A 0 , A 1 , … of set systems in X ( r ) as follows:
- Set A 0 = A.
- Having chosen A 0 , … , A k, if A k is U V-compressed for all ( U , V ) ∈ Γ then stop. Otherwise, choose U , V ∈ Γ with | U | = | V | > 0 minimal such that A k is not U V-compressed.
Note that ∀ ⁡ u ∈ U ∃ ⁡ v ∈ V such that ( U − u , V − v ) ∈ Γ (namely, use v = min ⁡ V). So (∗) is satisfied.
So Lemma 15 tells us that | ∂ C U V ( A k ) | ≤ | ∂ A k |.
Set A k + 1 = C U V ( A k ), and continue.
Must terminate, as ∑ ⁡ A ∈ A k ∑ i ∈ A 2 i is strictly decreasing. The final term B = A k satisfies | B | = | A |, | ∂ B | ≤ | ∂ A | and is U V-compressed for all ( U , V ) ∈ Γ.
So B = C by Lemma 14. □
nothing: True

html: Proposition 19. Assuming that:
- A ⊂ P ( X ) be intersecting
Then | A | ≤ 2 k − 1.
proof: Proof. For any A ⊂ X, at most one of A , A c can belong to A. □
cloze1: True

html: Theorem 20 (Erdos-Ko-Rado Theorem). Assuming that:
- A ⊂ X ( r ) be intersecting, where r < n 2
Then | A | ≤ n − 1 r − 1.
proof: Proof 1 (“Bubble down with Kruskal-Katona ”). Note that A ∩ B ≠ ∅ ⟺ A ⁄ ⊂ B c.
Let A ¯ = { A c : A ∈ A } ⊂ X ( n − r ). Have ∂ n − 2 r A ¯ and A are disjoint families of r-sets.
Suppose | A | > n − 1 r − 1. Then | A ¯ | = | A | > n − 1 r − 1 = n − 1 n − r. Whence by Kruskal-Katona we have | ∂ n − 2 r A ¯ | ≥ n − 1 r.
So | A | + | ∂ n − 2 r A ¯ | > n − 1 r − 1 + n − 1 r = n r, a contradiction. □
nothing: True

html: Theorem 1 (Harper’s Theorem). Assuming that:
- A ⊂ Q n
- C the initial segment of simplicial ordering with | C | = | A |
Then | N ( A ) | ≥ | N ( C ) |. In particular, if | A | = ∑ ⁡ i = 0 r n i then | N ( A ) | ≥ ∑ ⁡ i = 0 r + 1 n i.
proof: Proof. Induction on n: n = 1is trivial.
Given n > 1, and A ⊂ Q n, and 1 ≤ i ≤ n.
Claim: | N ( C i ( A ) ) | ≤ | N ( A ) |.
Proof of claim: Write B for C i ( A ). We have
N ( A ) − = N ( A − ) ∪ A + N ( A ) + = N ( A + ) ∪ A −
and of course
N ( B ) − = N ( B − ) ∪ B + N ( B ) + = N ( B + ) ∪ B −
Now, | B + | = | A + | and | N ( B − ) | ≤ | N ( A − ) | (by the induction hypothesis). But B + is an initial segment of simplicial ordering, and N ( B − ) is an initial segment of simplicial ordering (as neighbourhood of initial segment is an initial segment).
So then B + and N ( B − ) are nested (one conatined in the other). Hence | N ( B ) − | ≤ | N ( A ) − |. Similarly, | N ( B ) + | ≤ | N ( A ) + |.
Hence | N ( B ) | ≤ | N ( A ) |, which completes the proof of our claim. □
nothing: True

html: Lemma 2. Assuming that:
- B ⊂ Q n is i-compressed for all i
- B not an initial segment of the simplicial ordering
Then one of the following is true:
- either n is odd, say n = 2 k + 1, and B = X ( ≤ k ) − { k + 2 , k + 3 , … , 2 k + 1 } ∪ { 1 , 2 , … , k + 1 }
- or n is even, say n = 2 k, and B = X ( < k ) ∪ { x ∈ X ( k ) : 1 ∈ x } − { 1 , k + 2 , k + 3 , … , 2 k } ∪ { 2 , 3 , 4 , … , k + 1 }.
proof: Proof. Since B is not an initial segment of simplicial ordering, there exists x < y (in simplicial ordering) with x ∉ B, y ∈ B.
For each 1 ≤ i ≤ n: cannot have i ∈ x, i ∈ y (as B is i-compressed). Also cannot have i ∉ x, i ∉ y for the same reason.
So x = y c.
Thus: for each y ∈ B, there exists at most one earlier x with x ∉ B (namely x = y c). Similarly, for each x ∉ B there is at most one later y with y ∈ B (namely y = x c).
So B = { z : z ≤ y } − { x }, with x the predessor of y and x = y c.
Hence if n = 2 k + 1 then x is the last k-set, and if n = 2 k then x is the last k-set with 1. □
cloze1: True

html: Proposition 4. Assuming that:
- 0 < 𝜀 < 1 4
Then
∑ i = 0 ⌊ ( 1 2 − 𝜀 ) n ⌋ n i ≤ 1 𝜀 e − 𝜀 2 n 2 ⋅ 2 n .
proof: Proof. For i ≤ ⌊ ( 1 2 − 𝜀 ) n ⌋:
n i = n i i n − i + 1 ,
so
n i − 1 n i = i n − i + 1 ≤ ( 1 2 − 𝜀 ) n ( 1 2 + 𝜀 ) n = 1 2 − 𝜀 1 2 + 𝜀 = 1 − 2 𝜀 1 2 + 𝜀 ≤ 1 − 2 𝜀 .
Hence
∑ i = 0 ⌊ ( 1 2 − 𝜀 ) n ⌋ n i ≤ 1 2 𝜀 n ⌊ ( 1 2 − 𝜀 ) n ⌋
(sum of a geometric progression).
Same argument tells us that
n ⌊ ( 1 2 − 𝜀 ) n ⌋ ≤ n ⌊ ( 1 2 − 𝜀 2 ) n ⌋ ( 1 − 2 𝜀 2 ) 𝜀 n 2 − 1 -1 from the ⌊ ∙ ⌋ stuff ≤ 2 n ⋅ 2 ( 1 − 𝜀 ) 𝜀 n 2 ≤ 2 n ⋅ 2 e − 𝜀 2 n 2 as 1 − 𝜀 ≤ e − 𝜀
Thus
∑ i = 0 ⌊ ( 1 2 − 𝜀 ) n ⌋ n i ≤ 1 2 𝜀 ⋅ 2 e − 𝜀 2 n 2 ⋅ 2 n . □
cloze1: True

html: Theorem 5. Assuming that:
- 0 < 𝜀 < 1 4
- A ⊂ Q n
- | A | 2 n ≥ 1 2
Then | A ( 𝜀 n ) | 2 n ≥ 1 − 2 𝜀 e − 𝜀 2 n 2.
proof: Proof. Enough to show that if 𝜀 n an integer then
| A ( 𝜀 n ) | 2 n ≥ 1 − 1 𝜀 e − 𝜀 2 n 2 .
Have | A | ≥ ∑ ⁡ i = 0 ⌈ n 2 − 1 ⌉ n i, so by Harper’s Theorem, we have | A ( 𝜀 n ) | ≥ ∑ ⁡ i = 0 ⌈ n 2 − 1 + 𝜀 n ⌉ n i, so
| A ( 𝜀 n ) c | ≤ ∑ i = ⌈ n 2 + 𝜀 n ⌉ n n i = ∑ i = 0 ⌊ n 2 − 𝜀 n ⌋ n i ≤ 1 𝜀 e − 𝜀 2 n 2 2 n . □
cloze1: True

html: Theorem 6. Assuming that:
- f : Q n → ℝ Lipschitz with median M
Then
| { x : | f ( x ) − M | ≤ 𝜀 n } | 2 n ≥ 1 − 4 𝜀 e − 𝜀 2 n 2
for any 0 < 𝜀 < 1 4.
proof: Proof. Let A = { x : f ( x ) ≤ M }. Then | A | 2 n ≥ 1 2, so
| A ( 𝜀 n ) | 2 n ≥ 1 − 2 𝜀 e − 𝜀 2 n 2 .
ut f is Lipschitz, so x ∈ A ( 𝜀 n ) implies f ( x ) ≤ M + 𝜀 n. Thus
| { x : f ( x ) ≤ M + 𝜀 n } | 2 n ≥ 1 − 2 𝜀 e − 𝜀 2 n 2 .
Similarly,
| { x : f ( x ) ≥ M − 𝜀 n } | 2 n ≥ 1 − 2 𝜀 e − 𝜀 2 n 2 .
Hence
| { x : M − 𝜀 n ≤ f ( x ) ≤ M + 𝜀 n } | 2 n ≥ 1 − 4 𝜀 e − 𝜀 2 n 2 . □
cloze1: True

html: Proposition 7. Assuming that:
- t, α and G are such that for any Lipschitz function f : G → ℝ with median M we have
| { x ∈ G : | f ( x ) − M | > t } | | G | ≤ α ,
Then for all A ⊆ G with | A | | G | ≥ 1 2, we have | A ( t ) | | G | ≥ 1 − α.
proof: Proof. The function f ( x ) = d ( x , A ) is Lipschitz, and has 0 as a median, so
| { x ∈ G : x ∉ A ( t ) } | | G | ≤ α . □
cloze1: True

html: Theorem 8 (Edge-isoperimetric inequality in Q n). Assuming that:
- A ⊂ Q n
- let C the initial segment of binary on Q n with | C | = | A |
Then | ∂ C | ≤ | ∂ A |. In particular: if | A | = 2 k then | ∂ A | ≥ 2 k ( n − k ).
proof: Proof. Induction on n. n = 1 trivial.
For n > 1, A ⊂ Q n, 1 ≤ i ≤ n:
Claim: | ∂ B i ( A ) | ≤ | ∂ A |.
Proof of claim: write B for B i ( A ). .image Have
Also
| ∂ B | = | ∂ ( B − ) | + | ∂ ( B + ) | + | B + Δ B − | .
Now, | ∂ ( B − ) | ≤ | ∂ ( A − ) | and | ∂ ( B + ) | ≤ | ∂ ( A + ) | (induction hypothesis). Also, the sets B + and B − are nested (one is contained inside the other), as each is an initial segment of binary on P ( X − i ).
Whence we certainly have | B + Δ B − | ≤ | A + Δ A − |. So | ∂ B | ≤ | ∂ A |.
Define a sequence A 0 , A 1 , … ⊂ Q n as follows: set A 0 = A. Having defined A 0 , … , A k, if A k is i-binary compressed for all n then stop the sequence with A k. If not, choose i with B i ( A ) ≠ A and put A k + 1 = B i ( A k ). Must terminate, as the function k ↦ ∑ ⁡ x ∈ A k ( position of x in binary ) is strictly decreasing.
The final family B = A k satisfies | B | = | A |, | ∂ B | ≤ | ∂ A |, and B is i-binary compressed for all i.
Note that B need not be an initial segment of binary, for example { ∅ , 1 , 2 , 3 } ⊂ Q 3.
However:
Lemma 9. Assuming that:
- B ⊂ Q n is i-binary compressed for all i
- B not an initial segment of binary
Then B = P ( n − 1 ) − { 1 , 2 , 3 , … , n − 1 } ∪ { n } (“downstairs minus the last point, plus the first upstairs point”).
(Then done, as clearly | ∂ B | ≥ | ∂ C |, since C = P ( n − 1 )).
Proof. As B not an initial segment, there exists x < y with x ∉ B, y ∈ B. Then for all i: cannot have i ∈ x , y, and cannot have i ∉ x , y (as B is i-binary compressed).
Thus for each y ∈ B, there exists at most 1 earlier x ∉ B (namely x = y c). Also for each x ∉ B there is at most one later y ∈ B (namely y = x c).
Then x and y adjacent (since y is the unique element in B after x, and x is the unique element not in B before y).
So B = { z : z ≤ y } − { x }, where x is the predecessor of y and y = x c.
So must have y = { n }. □
This concludes the proof of Theorem 8. □
nothing: True

html: Lemma 9. Assuming that:
- B ⊂ Q n is i-binary compressed for all i
- B not an initial segment of binary
Then B = P ( n − 1 ) − { 1 , 2 , 3 , … , n − 1 } ∪ { n } (“downstairs minus the last point, plus the first upstairs point”).
proof: Proof. As B not an initial segment, there exists x < y with x ∉ B, y ∈ B. Then for all i: cannot have i ∈ x , y, and cannot have i ∉ x , y (as B is i-binary compressed).
Thus for each y ∈ B, there exists at most 1 earlier x ∉ B (namely x = y c). Also for each x ∉ B there is at most one later y ∈ B (namely y = x c).
Then x and y adjacent (since y is the unique element in B after x, and x is the unique element not in B before y).
So B = { z : z ≤ y } − { x }, where x is the predecessor of y and y = x c.
So must have y = { n }. □
cloze1: True

html: Theorem 11 (Vertex-isoperimetric inequality in the grid). Assuming that:
- A ⊂ [ k ] n
- C is the initial segment of simplicial order on [ k ] n with | C | = | A |
Then | N ( C ) | ≤ | N ( A ) |. In particular, if | A | ≥ | { x : | x | ≤ r } | then | N ( A ) | ≥ | { x : | x | ≤ r + 1 } |.
proof: Proof. Induction on n. For n = 1 it is trivial: if A ⊂ [ k ] 1 ≠ ∅ , [ k ] 1, then | N ( A ) | ≥ | A | + 1 = | N ( C ) |.
Given n > 1 and A ⊂ [ k ] n: fix 1 ≤ i ≤ n.
Claim: | N ( C i ( A ) | ≤ | N ( A ) |.
Proof of claim: write B for C i ( A ). For any 1 ≤ t ≤ k, we have
N ( A ) t = N ( A t ) ⏟ from x i = t ∪ A t − 1 ⏟ from x i = t − 1 ∪ A t + 1 ⏟ from x i = t + 1 .
(where A 0 , A k + 1 = ∅).
Also,
N ( B ) t = N ( B t ) ∪ B t − 1 ∪ B t + 1 .
Now, | B t − 1 | = | A t − 1 | and | B t + 1 | = | A t + 1 |, and | N ( B t ) | ≤ | N ( A t ) | (induction hypothesis). But the sets B t − 1, B t + 1, N ( B t ) are nested (as each is an initial segment of simplicial order on [ k ] n − 1).
Hence | N ( B ) t | ≤ | N ( A ) t | for each t. Thus | N ( B ) | ≤ | N ( A ) |.
Among all B ⊂ [ k ] n with | B | = | A | and | N ( B ) | ≤ | N ( A ) |, pick one that minimises the quantity ∑ ⁡ x ∈ B position of x in simplicial order.
Then B is i-compressed for all i. Note however, that this time we will make use of this minimality property of B for more than just deducing that B is i-compressed for all i.
Case 1: n = 2. What we know is precisely that B is a down-set (A ⊂ [ k ] n is a down-set if x ∈ A, y i ≤ x i ∀ ⁡ i ⟹ y ∈ A)
Let r = min ⁡ { | x | : x ∉ B } and s = max ⁡ { | x | : x ∉ B }. May assume r ≤ s, since r = s + 1 implies B = { x : | x | ≤ r − 1 } would imply B = C.
If r = s: then { x : | x | ≤ r − 1 } ⊂ B ⊂ { x : | x | ≤ r }. So clearly | N ( B ) | ≥ | N ( C ) |.
If r < s: cannot have { x : | x | = s } ⊂ B, because then also { x : | x | = r } ⊂ B (as B is a down-set).
So there exists y , y ′ with | y | = | y ′ | = s, y ∈ B, y ′ ∉ B and y ′ = y ± ( e 1 − e 2 ) (e 1 = ( 1 , 0 ), e 2 = ( 0 , 1 )).
Similarly, cannot have { x : | x | = r } ∩ B = ∅, because then { x : | x | = s } ∩ B = ∅ (as B is a down-set). So there exists x , x ′ with | x | = | x ′ | = r, x ∉ B, x ′ ∈ B and x ′ = x ± ( e 1 − e n ). Now let B ′ = B ∪ { x } − { y }. From B we lost ≥ 1 point in the neighbourhood (namely z in the picture), and gained ≤ 1 point (the only point that we can possibly gain is w), so | N ( B ′ ) | ≤ | N ( B ) |. This contradicts minimality of B. This finishes the two dimensional case.
Case 2: n ≥ 3. For any 1 ≤ i ≤ n − 1 and any x ∈ B with x n > 1, x i < k. Have x − r n + e i ∈ B (as B is j-compressed for any j, so apply with some j ≠ i , n). So, considering the n-sections of B, we have N ( B t ) ⊂ B t − 1 for all t = 2 , … , k.
Recall that N ( B ) t = N ( B t ) ∪ B t + 1 ∪ B t − 1. So in fact N ( B ) t = B t − 1 for all t ≥ 2. Thus
| N ( B ) | = | B k − 1 | ⏟ level k + | B k − 2 | ⏟ level k − 1 + ⋯ + | B 1 | ⏟ level 2 + | N ( B 1 ) | ⏟ level 1 = | B | − | B k | + | N ( B 1 ) | .
Similarly,
| N ( C ) | = | C | − | C k | + | N ( C 1 ) | .
So to show | N ( C ) | ≤ | N ( B ) |, enough to show that | B k | ≤ | C k | and | B 1 | ≥ | C 1 |.
| B k | ≤ | C k |: define a set D ⊂ [ k ] n as follows: put D k = B k, and for t = k − 1 , k − 2 , … , 1 set D t = N ( D t − 1 ). Then D ⊂ B, so | D | ≤ | B |. Also, D is an initial segment of simplicial order. So in fact D ⊂ C, whence | B k | = | D k | ≤ | C k |.
| B 1 | ≥ | C 1 |: define a set E ⊂ [ k ] n as follows: put E 1 = B 1 and for t = 2 , 3 , … , k set E t = { x ∈ [ k ] n − 1 : N ( { x } ) ⊂ E t − 1 } (E t is the biggest it could be given N ( E t ) ⊂ E t). Then E ⊃ B, so | E | ≥ | B |. Also, E is an initial segment of simplicial order. So E ⊃ C, whence | B 1 | = | E 1 | ≥ | C 1 |. □
nothing: True

html: Theorem 13. Assuming that:
- A ⊂ [ k ] n
- | A | ≤ k n 2
Then
| ∂ A | ≥ min ⁡ { d | A | 1 − 1 d k n d − 1 : 1 ≤ d ≤ n } .
proof: Proof (sketch). Induction on n. n = 1 is trivial.
Given A ⊂ [ k ] n with | A | ≤ k n 2, where n > 1:
Wlog A is a down-set (just down-compress, i.e. stamp on your set in direction i for each i). For any 1 ≤ i ≤ n, define C i ( A ) ⊂ [ k ] n by giving its i-sections:
C i ( A ) t = extremal set of size | A t | in [ k ] n − 1 ,
which will be a set of the form [ a ] d × [ k ] n − 1 − d, or a complement. Write B = C i ( A ). Do we have | ∂ B | ≤ | ∂ A |?
Now, A is a down-set, so
| ∂ A | = | ∂ A 1 | + ⋯ + | ∂ A k | ⏟ horizontal edges + | A 1 | − | A k | ⏟ vertical edges
and
| ∂ B | = | ∂ B 1 | + ⋯ + | ∂ B k | + ?
The ? is because B not a down-set, as extremal sets in dimension n − 1 are not nested.
Indeed, can have | ∂ B | > | ∂ A |:
Idea: try to introduce a “fake” boundary ∂ ′: want ∂ ′ A ≤ ∂ A, with ∂ ′ = ∂ on extremal sets, such that C i does decrease ∂ ′ (then done).
Try ∂ ′ A = ∑ ⁡ t | ∂ A t | + | A 1 | − | A k |. Then ∂ ′ A ≤ | ∂ A | for all A, equality for extremal sets (as equality for any down-set) and ∂ ′ C i ( A ) ≤ ∂ ′ A. But: fails for C j ( A ) for all j ≠ i.
Could try to fix this by defining ∂ ″ A = ∑ ⁡ i ( | A 1 ( i ) | − | A k ( i ) | ). Also fails – for example if A is the “outer shell” of [ k ] n then ∂ ″ A = 0.
So far, have
| ∂ A | ≥ ∂ ′ A ≥ ∂ ′ B = ∑ t | ∂ B t | + | B 1 | − | B k | = ∑ t f ( | B t | ) + | B 1 | − | B k |
where f is the extremal function in [ k ] n − 1.
Now, f is the pointwise minimum of some functions of the form c x 1 − 1 d and c ( k n − 1 − x ) 1 − 1 d – each of which is a concave function. Hence f itself is a concave function.
Consider varying | B 2 | , … , | B k − 1 |, keeping | B 2 | + ⋯ + | B k − 1 | constant and keeping | B 1 | ≥ | B 2 | ≥ ⋯ ≥ | B k − 1 | ≥ | B k |.
We obtain ∂ ′ B ≥ ∂ ′ C, where for some λ,
C t = { B 1 ∀ ⁡ 1 ≤ t ≤ λ B k ∀ ⁡ λ + 1 ≤ t ≤ k
So:
| ∂ A | = ∂ ′ A ≥ ∂ ′ B ≥ ∂ ′ C = λ f ( | B 1 | ) + ( k − λ ) f ( | B k | ) + | B 1 | − | B k |
but C is still not a down-set.
Now vary, | B 1 |, keeping λ | B 1 | + ( k − λ ) | B k | fixed (λ fixed) and | B 1 | ≥ | B k |.
This is a concave function of | B 1 | – as concave + concave + linear. Hence “make | B 1 | as small or large as possible”.
i.e. ∂ ′ C ≥ ∂ ′ D, where one of the following holds:
- D t = D 1 for all t
- D t = D 1 for all t ≤ λ, D t = ∅ for all t > λ
- D t = [ k ] n − 1 for all t ≤ λ, D t = D k for all t > λ.
But (miraculously), this D is a down-set!
Hence
| ∂ A | = ∂ ′ A ≥ ∂ ′ B ≥ ∂ ′ C ≥ ∂ ′ D = | ∂ D | .
So our “compression in direction i” is: A ↦ D.
Now finish as before. □
cloze1: True

html: Theorem 1 (Katona’s t-intersecting Theorem). Assuming that:
- A ⊂ P ( X ) is t-intersecting
- n + t even (to make the proof simpler – same proof works for odd)
Then | A | ≤ | X ( ≥ n + t 2 ) |.
proof: Proof. For any x , y ∈ A: have | x ∩ y | ≥ t, so d ( x , y c ) ≥ t. So, writing A ¯ for { y c : y ∈ A }, have d ( A , A ¯ ) ≥ t – i.e. A ( t − 1 ) disjoint from A ¯. Suppose that | A | > | X ( ≥ n + t 2 ) |.
Then, by Harper’s Theorem, we have
| A ( t − 1 ) | ≥ | X ( ≥ n + t 2 − ( t − 1 ) ) | = | X ( ≥ n − t 2 + 1 ) | .
But A ( t − 1 ) disjoint from A ¯, which has size > | X ( ≤ n − t 2 ) | contradicting | A ( t − 1 ) | + | A ¯ | ≤ 2 n. □
nothing: True

html: Theorem 2. Assuming that:
- A ⊂ X ( r ) is t-intersecting
Then for n sufficiently large, we have | A | ≤ | A 0 | = n − t r − t.
proof: Proof. Extending A to a maximal t-intersecting family, we must have some x , y ∈ A with | x ∩ y | = t (if not, then by maximality have that ∀ ⁡ x ∈ A, ∀ ⁡ i ∈ x, ∀ ⁡ j ∉ x, have x ∪ j − i ∈ A – whence A = X ( r ), contradiction).
May assume that there exists z ∈ A with x ∩ y ⁄ ⊂ z – otherwise all z ∈ A have x ∩ y ⊂ z. Whence | A | ≤ n − t r − t = | A 0 |.
So each w ∈ A must meet x ∪ y ∪ z in ≥ t + 1 points. Thus
| A | ≤ 2 3 r ⏟ w on x ∪ y ∪ z ( n r − t − 1 + n r − t − 2 + ⋯ + n 0 ⏟ w off x ∪ y ∪ z ) .
Note that the right hand side is a polynomial of degree r − t − 1 – so eventually beaten by | A 0 |. □
cloze1: True

html: Proposition 3. Assuming that:
- r is odd
- A ⊂ X ( r ) such that | x ∩ y | for each distinct x , y ∈ A
Then | A | ≤ n.
proof: Proof. View P ( X ) as ℤ 2 n, the n-dimensional space over ℤ 2 (the field of order 2). By identifying x with x ¯, its characteristic sequence (e.g. 1 0 1 1 0 0 0 … for { 1 , 3 , 4 }).
We have ( x ¯ , x ¯ ) ≠ 0 for each x, as r is odd (( ∙ , ∙ ) is the usual dot-product).
Also, ( x ¯ , y ¯ ) = 0 for distinct x , y ∈ A (as | x ∩ y | even).
Hence the x ¯, x ∈ A are linearly independent (if ∑ ⁡ λ i x i ¯ = 0, dot with x j ¯ to get λ j = 0). □
cloze1: True

html: Theorem 4 (Frankl-Wilson Theorem). Assuming that:
- p is prime
- λ 1 , … , λ s (s ≤ r)
- λ i ⁄ ≡ r ( m o d p ) for each i
- A ⊂ X ( r ) such that for all distinct x , y ∈ A have | x ∩ y | ≡ λ i ( m o d p ) for some i
Then | A | ≤ n s.
proof: Proof. For each i ≤ j, let M ( i , j ) be the n i × n j matrix, with rows indexed by X ( i ), columns indexed by X ( j ), with
M ( i , j ) x y = { 1 if x ⊂ y 0 otherwise
for each x ∈ X ( i ), y ∈ X ( j ).
Let V be the vector space (over ℝ) spanned by the rows of M ( s , r ). So dim ⁡ V ≤ n s.
For i ≤ s, consider M ( i , s ) M ( s , r ) (note each row belongs to V, as we premultiplied M ( s , r ) by a matrix). For x ∈ X ( i ), y ∈ X ( r ):
( M ( i , s ) M ( s , r ) ) x y = # of s -sets z with x ⊂ z and z ⊂ y = { 0 if x ⁄ ⊂ y r − i s − i if x ⊂ y
So
M ( i , s ) M ( s , r ) = r − i s − i M ( i , r )
so all rows of M ( i , r ) belong to V.
Let M ( i ) = M ( i , r ) ⊤ ⁡ M ( i , r ) (note each row is in V).
For x , y ∈ X ( r ), have
M ( i ) x y = # i -sets z with z ⊂ x , z ⊂ y = | x ∩ y | i
Write the integer polynomial ( t − λ 1 ) ⋯ ( t − λ s ) as ∑ ⁡ i = 0 s a i t i, with a i ∈ ℤ – possible because t ( t − 1 ) ⋯ ( t − i + 1 ) = i ! t i.
Let M = ∑ ⁡ i = 0 s a i M ( i ) (each row is in V).
Then for all x , y ∈ X ( r ):
M x y = ∑ i a i | x ∩ y | i = ( | x ∩ y | − λ i ) ⋯ ( | x ∩ y | − λ s ) .
So the submatrix of M spanned by the rows and columns corresponding to the elements of A is
( ⁄ ≡ 0 0 ⋯ 0 0 ⁄ ≡ 0 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ ⁄ ≡ 0 ) .
Hence the rows of M corresponding to A are linearly independent over ℤ p, so also over ℤ, so also over ℚ, so also over ℝ.
So | A | ≤ dim ⁡ V ≤ n s. □
nothing: True

html: Theorem 7 (Kahn, Kalai 1995). Assuming that:
- n ∈ ℕ
Then there exists bounded S ⊂ ℝ n such that to break S into pieces of smaller diameter we need ≥ C n, for some constant c > 1 (not depending on n).
proof: Proof. We’ll find S ⊂ Q n ⊂ ℝ n – in fact S ⊂ [ n ] ( r ) for some r. We have already had two genuine ideas from this sentence: first that we think about having S ⊂ Q n, and second that we go for S ⊂ [ n ] ( r ).
Have S ⊂ [ n ] ( r ), so ∀ ⁡ x , y ∈ S:
∥ x − y ∥ 2 = # coordinates where x and y differ = 2 ( r − | x ∩ y | ) .
So seek S with diameter min ⁡ | x ∩ y | = k, but every subset of S with min ⁡ | x ∩ y | > k is very small (hence we will need many pieces).
Identify [ n ] with the edge-set of K 4 p, the complete graph on 4 p points.
For each x ∈ [ 4 p ] ( 2 p ) let G x be the complete bipartite graph, with vertex classes x , x c. Let S = { G x : x ∈ [ 4 p ] ( 2 p ) }. So S ⊂ [ n ] ( 4 p 2 ), and | S | = 1 2 4 p 2 p.
Now
| G x ∩ G y | = | x ∩ y | | x c ∩ y c | + | x c ∩ y | | x ∩ y c | = | x ∩ y | 2 + | x c ∩ y | 2 = d 2 + ( 2 p − d ) 2
where d = | x ∩ y |.
This is minimised when d = p, i.e. when | x ∩ y | = p.
Now let S ′ ⊂ S have smaller diameter than that of S: say S ′ = { G x : x ∈ A }. So must have ∀ ⁡ x , y ∈ A distinct: | x ∩ y | ≠ p (else diameter of S ′ is the diameter of S).
Thus
| A | ≤ 2 4 p p − 1 .
Conclusion: the number of pieces needed is ≥ 1 2 4 p 2 p 2 4 p p − 1 ≥ c ⋅ 2 4 p ∕ p e − p ∕ 8 2 4 p (for some c). This is ≥ ( c ′ ) p, for some c ′ > 1, which is at least ( c ″ ) n for some c ″ > 1. □
nothing: True