Title: Daniel's Flashcards / Year 5 / Term 1 / Probabilistic Combinatorics

html: Definition 1.1 (Independence number). Let G be a graph. Then I ⊂ V ( G ) is independent if x ⁄ ∼ y in G for all x , y ∈ I.
We use α ( G ) = size of the largest independent set.
nothing: True

html: Lemma 1.2. Assuming that:
- 1 n ≪ p ≤ 1 2
- G ∼ G ( n , p )
Then
α ( G ) ≤ ( 2 + o ( 1 ) ) log ⁡ n p p ,
with probability tending to 1 as n → ∞ (known as “with high probability (w.h.p.)”).
proof: Proof. Let k = ( 2 + δ ) log ⁡ n p p, for some δ > 0. Let X be the random variable that counts the number of independent k sets in G.
𝟙 𝔼 X = 𝔼 ∑ I ∈ [ n ] ( k ) 𝟙 I is independent = ∑ I ∈ [ n ] ( k ) ℙ ( I is independent ) = n k ( 1 − p ) k 2 ≤ ( e n k ) k e − p k 2 ≤ ( e n k ⋅ e − ( k − 1 2 ) p ) k → 0
by plugging in k. So by Markov
ℙ ( X ≥ 1 ) ≤ 𝔼 X → 0 . □
cloze1: True

html: Lemma 1.3. Assuming that:
- 1 n ≪ p ≤ 1
- G ∼ G ( n , p )
Then
# triangles in G = ( 1 + o ( 1 ) ) p 3 n 3
with high probability.
proof: Proof. Let X be the random variable counting the number of triangles in G. Note
𝟙 X = ∑ T ∈ [ n ] ( 3 ) 𝟙 T ( 2 ) ⊂ G .
Mean is straightforward:
𝔼 X = p 3 n 3 .
Variance is a little more tricky. First:
𝟙 X 2 = ∑ S , T ∈ [ n ] ( 3 ) 𝟙 S ( 2 ) , T ( 2 ) ⊂ G .
We can write
𝔼 X 2 = ∑ S , T ∈ [ n ] ( 2 ) ℙ ( T ( 2 ) , S ( 2 ) ⊂ G ) ( 𝔼 X ) 2 = ∑ S , T ∈ [ n ] ( 2 ) ℙ ( T ( 2 ) ⊂ G ) ℙ ( S ( 2 ) ⊂ G )
Since the pairs of events are independent whenever | S ( 2 ) ∩ T ( 2 ) | = 0, we have
Var ⁡ X ≤ ∑ S , T ∈ [ n ] ( 2 ) | S ( 2 ) ∩ T ( 2 ) | = 1 ≤ p 5 n 4 + 𝔼 X Now note ℙ ( | X − 𝔼 X | ≥ δ 𝔼 X ) ≤ Var ⁡ X δ 2 ( 𝔼 X ) 2 ≤ p 5 n 4 δ 2 ( 𝔼 X ) 2 + 1 δ 2 𝔼 X ≤ C p 5 n 4 ( n 3 p 3 ) 2 + 1 δ 2 𝔼 X ≤ C 1 n 2 p + 1 δ 2 𝔼 X → 0 □
cloze1: True

html: Theorem 1.4 (Erdos, 1960s). R ( 3 , k ) ≥ c k 2 ( log ⁡ k ) 2 for some c > 0.
proof: Proof. Fix t = p k 2 1 6 and fix a set S with size | S | = k.
ℙ ( e ( G [ S ] ) < t ) ≤ ∑ i = 0 t k 2 i p i ( 1 − p ) k 2 − i ≤ t k 2 t p t ( 1 − p ) k 2 − t ≤ t [ ( e k 2 2 t ) t p t ] e − p [ k 2 − t ] ≤ t ( e 8 ) p k 2 1 6 e − p k 2 ∕ 2 ≤ k 2 [ ( e 8 ) 1 e − 4 + o ( 1 ) ] p k 2 1 6 ≤ e − α p k 2
for some α > 0.
We now union bound on all S ∈ [ n ] ( k ).
ℙ ( ∃ ⁡ S ∈ [ n ] ( k ) such that e ( [ S ] ) < t ) ≤ n k ℙ ( e ( G [ S ] ) < t ) ≤ ( e n k ) k e − α k 2 p = ( e n k ⋅ e − α k p ) k ≤ ( e n p ( 1 p n ) α C ) k
(using k p ≥ C log ⁡ n) which → 0 for C > 1 α. □
nothing: True

html: Lemma 1.5. Assuming that:
- 1 n ≪ p ≤ 1 2
- G ∼ G ( n , p )
- k > C log ⁡ n p
Then with high probability every set of size ≥ k in G induces p k 2 1 6 edges.
proof: Proof. Fix t = p k 2 1 6 and fix a set S with size | S | = k.
ℙ ( e ( G [ S ] ) < t ) ≤ ∑ i = 0 t k 2 i p i ( 1 − p ) k 2 − i ≤ t k 2 t p t ( 1 − p ) k 2 − t ≤ t [ ( e k 2 2 t ) t p t ] e − p [ k 2 − t ] ≤ t ( e 8 ) p k 2 1 6 e − p k 2 ∕ 2 ≤ k 2 [ ( e 8 ) 1 e − 4 + o ( 1 ) ] p k 2 1 6 ≤ e − α p k 2
for some α > 0.
We now union bound on all S ∈ [ n ] ( k ).
ℙ ( ∃ ⁡ S ∈ [ n ] ( k ) such that e ( [ S ] ) < t ) ≤ n k ℙ ( e ( G [ S ] ) < t ) ≤ ( e n k ) k e − α k 2 p = ( e n k ⋅ e − α k p ) k ≤ ( e n p ( 1 p n ) α C ) k
(using k p ≥ C log ⁡ n) which → 0 for C > 1 α. □
cloze1: True

html: Lemma 1.6. Assuming that:
- F = { A i } i be a collection of events
- E t, for t ∈ ℕ, be the event that t independent events of F occur
Then
ℙ ( E t ) ≤ 1 t ! ( ∑ i ℙ ( A i ) ) t .
proof: Proof. Let I = { ( A i 1 , … , A i k ) : A i 1 , … , A i k are independent }.
𝟙 𝟙 𝟙 E t ≤ 1 t ! ∑ ( A i 1 , … , A i k ∈ I 𝟙 A i 1 ∩ ⋯ ∩ A i k ℙ ( E t ) ≤ ∑ ( A i 1 , … , A i k ) ∈ I ℙ ( A i 1 ∩ ⋯ ∩ A i k ) ≤ 1 t ! ∑ i 1 , … , i t ℙ ( A i 1 ) ⋯ ℙ ( A i k ) = 1 t ! ( ∑ i ℙ ( A i ) ) t □
cloze1: True

html: Theorem. Assuming that:
- n ≥ 2
Then there exists a triangle-free graph G on n vertices with
α ( G ) ≤ C n log ⁡ n .
proof: Proof. Let n be large. Let p = γ n for some γ > 0. Let G ∼ G ( n , p ), and let G ~ be G with a maximal collection of edge disjoint triangles T removed, i.e. G ~ = G − T.
Clearly G ~ is triangle-free. We let Q be the event that every set of size k, where k = C n log ⁡ n contains at least p k 2 1 6 edges. We now consider
ℙ ( α ( G ~ ) ≥ k ) = ℙ ( α ( G ~ ) ≥ k ∩ Q ) + ℙ ( α ( G ~ ) ≥ k ∩ Q c ) .
So
ℙ ( α ( G ~ ) ≥ k ) ≤ ℙ ( α ( G ~ ) ≥ k ∩ Q ) ⏟ ( ∗ ) + o ( 1 ) .
We now union-bound
( ∗ ) ≤ n k ℙ ( I independent in G ~ ∩ Q ) = n k ℙ ( T intersects I in ≥ p k 2 1 6 edges )
Define { T i } to be the collection of all triangles that meet I in at least one edge, and define the event A i = { T i ⊂ G }.
Note that the event E t, where t = p k 2 1 6, from the lemma holds on the event that T meets I in p k 2 1 6 edges. This is where we use the fact that we only choose edge-disjoint triangles! By Lemma 1.6, we have
ℙ ( E t ) ≤ 2 ( e k 2 n p 3 t ) t ≤ ( 1 6 e k 2 n p 3 p k 2 ) p k 2 1 6 = ( 1 6 e γ 2 ) p k 2 1 6
So
( ∗ ) ≤ ( 1 6 e γ 2 ) p k 2 1 6 ( e n k ) k → 0 ,
if γ is chosen to be small and C large. □
cloze1: True