Combinatorics chapter 3 ideas of proofs Flashcards
idea of proof for radons lemma
- There exists λᵢs not all zero such that the sum over i in [d+2] of λᵢaᵢ = 0 and the sum over i in [d+2] of λᵢ = 0. Note there are d+1 equations and d+2 unknowns λᵢ.
- Make two sets for the i’s when λᵢ is positive and when λᵢ is negative (P,N)
- Define A₁ and A₂ for the positive and negative indices
- Show that the convex hull of A₁ and A₂ both contain a point p (normalise the sums to get get elements in A₁ and A₂)
idea of proof for hellys theorem
- fix d and induct on n. When n=d+1, it holds trivially. So assume n>d+1.
- for every iϵ[n] let aᵢ be in the intersection of the cⱼs for j≠i
- By radons lemma there exists disjoint sets I₁ I₂ s.t. the intersection of the convex hulls of aᵢ for iϵI₁,I₂ is non empty.
- Let x be an element in this intersection
- We claim xϵcᵢ for all iϵ[n].
- For iϵ[n] note i∉I₁ or i∉I₂. If i∉I₁ then for all jϵI₁ aⱼ is an element of the intersection of c’ⱼ for j’≠j.
- Now since xϵconv({aⱼ: jϵI₁}) we have xϵcᵢ
idea of proof for caratheodorys theorem
- consider a point in X. Write this point as a convex combination of elements of X.
- Assume t is minimal (where t is the number of elements in X) assume for a contradiction t≥d+2.
- Then there exists μs (not all 0) such that the combination of xs&μs is 0 and the sum of the μs is also 0. Note there exists a solution to this series of equations.
- for α real we have that the sum over i in [t] (λᵢ - αμᵢ)=1 and the sum over i in [t] (λᵢ - αμᵢ)xᵢ = x
- We can choose α such that (λᵢ - αμᵢ)≥0 and at least one term equal to zero. This means that one term in the convex combination of x is not needed, contradicting the minimality of t => t≤d+1.
idea of proof for prop 3.6. I(3,3)=6.
[lower bound] give an example e.g. 3 points in a triangle with a line going through two points each.
[upperbound] take the cases where each line contains at most 2 points I(P,L)≤3x2 and there exists a line with all the points on it I(P,L)≤3+1+1=5
idea of proof for lemma 3.7. I(m,n)≤n √(m) + m.
- suppose I(P,L) is maximum
- suppose that each point in P has dᵢ indicies. maximality dᵢ≥1 for all i.
- there are at most n choose 2 crossing pairs of lines
- a point with dᵢ incidences gives rise to dᵢ choose 2 crossing pairs.
- therefore we can get that the sum over i in [m] (dᵢ-1)² ≤ n² (Use sum over i in [m] dᵢ choose 2 >= 1/2 sum over i in [m] (dᵢ-1) ² and (n choose 2)<= n²/2)
- applying cauchy-scwarz and maninpulating we get that I(m,n)=I(P,L) = sum over i in [m] dᵢ = sum over i in [m] (dᵢ-1) + m ≤ m + (sum over i in [m] (d ᵢ-1)² m)¹/² ≤ m + n √(m)
idea of proof for prop 3.9. if n=4k³ I(n,n) ≥ (n⁴/³) / (³√4)
- define the set of points (kx4k²) grid and the set of lines y=ax+b for aϵ[2k] bϵ[2k²]
- note |P|=n=4k³=|L|
- consider any line for xϵ[k] we have ax+b≤4k².
- I(P,l) = k because l contains exactly k points of P, namely one for each x.
- so I(P,L)= sum of all lines I(P,l)=k * |L|
idea of proof for corollary 3.10 The number of triples spanning a triangle of unit area is at most 20n⁷/³.
- fix a vertex p.
- the for each point q define two parallel lines above and below the line with vertical distance 2/|p-q| to line pq.
- Count the number of unit triangles i.e., the number of points on these two lines = I(P{p},L).
- Bound this from above via the Szemeredi-Trotter Theorem
- repeat for all p
idea of proof for proposition 3.11. 2|A|-1 ≤ |A+A|,|A.A|≤ |A|(|A|+1)/2. [lower bound]
- Let A = {a₁,…,aₗ} with a₁ the smallest and aₗ the biggest
- consider a₁+a₁ and increase the index of the second term until it reaches aₗ then increase the index of 1st term until it reaches aₗ
- there are 2l-1 terms in this sequence so |A+A|>= 2|A|-1
idea of proof for proposition 3.11. 2|A|-1 ≤ |A+A|,|A.A|≤ |A|(|A|+1)/2. [upper bound]
- Let A = {a₁,…,aₗ}
- |A+A|≤#of ways of picking two members with repetition ≤ |A| + (|A| choose 2) = |A|(|A|+1)/2
idea of proof for theorem 3.12. max{|A+A|,|A.A|}≥1/8|A|⁵/⁴
- it suffices to show that |A+A|.|A.A|≥ 1/64 |A|⁵/²
- Let P = (A+A)x(A.A)⊆ℝ² Then |P| = |A+A|.|A.A|
- Let L be the set of lines of the form x=a+t and y=a’t for a,a’ϵA. Then |L|=|A|².
- an incidence with P and L occurs only when t∈A
- For each line in L when t∈A then x∈A+A and y∈A.A so each line will intersect |A| points in P: I(P,L)=|A||L|=|A|³
- We know |L|<=|P|<=|L|² (previous result)
- Apply Szemeredi Trotter and rearrange for |P| to get answer (using above point)
A₁ and A₂ in proof of radons lemma
A₁={aᵢ: iϵP}
A₂={aⱼ: jϵN}
P and N in proof of radons lemma
P={iϵ[d+2]:λᵢ>0}
N={jϵ[d+2]:λᵢ<0}
Λ in proof of radons lemma
sum over all i in P of λᵢ = minus the sum over all j in N of λⱼ
point that lies in the convex hulls of A₁ and A₂ proof of radons lemma
p = sum over i in P of λᵢ/Λ * aᵢ = sum over j in p of -λⱼ/Λ * aⱼ
aim of radons lemma proof
define an A₁ and A₂ such that their convex hulls contain a common point
set up of in proof of radons lemma
Let A={a₁,..,aₔ₊₂} there exists λ₁,…,λₔ₊₂ not all zero such that the sum over i in [d+2] of λᵢaᵢ = 0 and the sum over i in [d+2] of λᵢ = 0
Last part of Proof of Hellys Theorem
Consider iϵ[n]. Note that, i∉I₁ or i∉I₂.
So assume i∉I₁.
For jϵI₁ we have aⱼ is an element of the intersection of all cⱼ’ where j’≠j.
I.e, aⱼ is in cᵢ.
Now xϵconv({aⱼ: jϵI₁}) so xϵcᵢ.
Applying Radons Lemma in proof of Hellys Theorem
By radons lemma there exists disjoint sets I₁,I₂⊆[n] s.t. the intersection of the convex hulls of aᵢ for iϵI₁,I₂ is non empty.
Set up in proof of Hellys Theorem.
Fix d proceed by induction on n.
When n=d+1 the theorem holds trivially. So assume n>d+1.
For iϵ[n] let aᵢϵ Intersection over j≠i of cⱼ.
Main point in proof of caratheodorys theorem
Assume t is minimal. If t<=d+1 we are done. Then suppose for a contradiction t≥d+2.
If t≥d+2 then in proof of caratheodorys theorem (middle part of proof)
Then there exists a real number µ₁,..,µₜ not all zero such that
the sum over all i in t of µᵢ =0 and the sum over all i in t of µᵢxᵢ=0.
Note as we have t≥d+2 unknowns and d+1 equations there is a solution.
Choose an α in proof of caratheodorys theorem
For all α real such that the sum of all i in t of λᵢ - αµᵢ =1 and the sum of all i in t of (λᵢ - αµᵢ)xᵢ =x.
Then we can choose an α s.t. (λᵢ - αμᵢ)≥0
Set up for proof of I(m,n)≤n √(m) + m.
Let P={p₁,..,pₘ} be a set of m points in the plane.
Let L={l₁,..,lₙ} be a set of n points in the plane.
Suppose I(P,L) is maximum.
Suppose each point pᵢ in P has dᵢ incidences.(n choose 2) ≤
proof of I(m,n)≤n √(m) + m
(n choose 2) ≤ n²/2
sum over all i in m of (dᵢ choose 2) ≥
proof of I(m,n)≤n √(m) + m
sum over all i in m of (dᵢ choose 2) ≥ 1/2 the sum over all i in m of (dᵢ-1)².
Set up for proof of if n=4k³ I(n,n) ≥ (n⁴/³) / (³√4)
Let P={(i,j): iϵ[k], iϵ[4k²]} be the kx4k² grid.
Let L be the set of lines with equation y=ax+b with aϵ[2k] and bϵ[2k²].
lq and lq’ in proof that the number of triples spanning a triangle of unit area is at most 20n⁷/³.
the lines parallel to pq at distance 2/|p-q| from it.
Lₚ =
in proof that the number of triples spanning a triangle of unit area is at most 20n⁷/³.
Lₚ = {lq, lq’: qϵP{p}}
|Lₚ|
in proof that the number of triples spanning a triangle of unit area is at most 20n⁷/³.
2(n-1)
#of unit triangles containing p = in proof that the number of triples spanning a triangle of unit area is at most 20n⁷/³.
of unit triangles containing p ≤ # of incidences of lq and lq’ = I (P{p}, Lₚ)
To prove theorem: max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴
It suffices to show….
It suffices to show |A+A|,|A.A|≥1/64|A|⁵/²
P in proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴
Let P=(A+A)x(A.A)⊆ℝ² so |P|=|A+A|x|A.A|
L in proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴
Let L be the set of lines of the form x=a+t and y=a’t for a,a’ϵA.
So |L|=|A|²
First part of proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴
for each line in L when tϵA then xϵA+A and yϵA.A. Hence each line will contain exactly |A| points in P. I(P,l)=|A| => I(P,L)= |A|.|L|=|A|³
second part of proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴
Note, |L|=|A|²≤|P|. So I(P,L)≤4(|P|²/³|L|²/³+|P|+|L|)≤12|P|²/³|L|²/³
Set up for caratheodorys proof
Consider a point xϵX. Suppose x₁,..,xₜϵX and λ₁,…,λₜ>0 s.t. x= the sum over iϵ[t] of xᵢλᵢ and 1=the sum over iϵ[t] of λᵢ
sum over i in [m] dᵢ choose 2 >=
proof of I(m,n)≤n √(m) + m
sum over i in [m] dᵢ choose 2 >= 1/2 sum over i in [m] (dᵢ-1) ²
proof of I(m,n)≤n √(m) + m quick points
- define maximum possible number of crossing lines
- define a point with dᵢ incidences gives rise to a certain number of crossing pairs
- show the sum over i in [m] (dᵢ-1)² ≤ n²
- Use cauchy schwarz and the above to show result
I(P,L)= sum over i in [m] of dᵢ where dᵢ is
each point pᵢ has dᵢ incidences.
There are at most _____ crossing pairs of lines in the plane.
(proof of I(m,n)≤n √(m) + m)
n choose 2
A point pᵢ in P with dᵢ incidences gives rise to ____ crossing pairs of lines.
(proof of I(m,n)≤n √(m) + m)
dᵢ choose 2
I(P,l)=
proof of if n=4k³ I(n,n) ≥ (n⁴/³) / (³√4)
k because l contains exactly k points of P, namely one for each x.
consider a line l in L the for all i in [k] we have ai+b≤
proof of if n=4k³ I(n,n) ≥ (n⁴/³) / (³√4)
ak+b≤2k.2k+2k²=4k²
For each line in L when t∈A then
proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴
For each line in L when t∈A then x∈A+A and y∈A.A so each line will intersect |A| points in P: I(P,L)=|A||L|=|A|³
