Combinatorics chapter 3 ideas of proofs

Question 1

idea of proof for radons lemma

Answer 1

1. 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 λᵢ.
2. Make two sets for the i’s when λᵢ is positive and when λᵢ is negative (P,N)
3. Define A₁ and A₂ for the positive and negative indices
4. 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₂)

Question 2

idea of proof for hellys theorem

Answer 2

• 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ᵢ

Question 3

idea of proof for caratheodorys theorem

Answer 3

1. consider a point in X. Write this point as a convex combination of elements of X.
2. Assume t is minimal (where t is the number of elements in X) assume for a contradiction t≥d+2.
3. 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.
4. for α real we have that the sum over i in [t] (λᵢ - αμᵢ)=1 and the sum over i in [t] (λᵢ - αμᵢ)xᵢ = x
5. 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.

Question 4

idea of proof for prop 3.6. I(3,3)=6.

Answer 4

[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

Question 5

idea of proof for lemma 3.7. I(m,n)≤n √(m) + m.

Answer 5

1. suppose I(P,L) is maximum
2. suppose that each point in P has dᵢ indicies. maximality dᵢ≥1 for all i.
3. there are at most n choose 2 crossing pairs of lines
4. a point with dᵢ incidences gives rise to dᵢ choose 2 crossing pairs.
5. 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)
6. 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)

Question 6

idea of proof for prop 3.9. if n=4k³ I(n,n) ≥ (n⁴/³) / (³√4)

Answer 6

1. define the set of points (kx4k²) grid and the set of lines y=ax+b for aϵ[2k] bϵ[2k²]
2. note |P|=n=4k³=|L|
3. consider any line for xϵ[k] we have ax+b≤4k².
4. I(P,l) = k because l contains exactly k points of P, namely one for each x.
5. so I(P,L)= sum of all lines I(P,l)=k * |L|

Question 7

idea of proof for corollary 3.10 The number of triples spanning a triangle of unit area is at most 20n⁷/³.

Answer 7

1. fix a vertex p.
2. the for each point q define two parallel lines above and below the line with vertical distance 2/|p-q| to line pq.
3. Count the number of unit triangles i.e., the number of points on these two lines = I(P{p},L).
4. Bound this from above via the Szemeredi-Trotter Theorem
5. repeat for all p

Question 8

idea of proof for proposition 3.11. 2|A|-1 ≤ |A+A|,|A.A|≤ |A|(|A|+1)/2. [lower bound]

Answer 8

• 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

Question 9

idea of proof for proposition 3.11. 2|A|-1 ≤ |A+A|,|A.A|≤ |A|(|A|+1)/2. [upper bound]

Answer 9

• Let A = {a₁,…,aₗ}

- |A+A|≤#of ways of picking two members with repetition ≤ |A| + (|A| choose 2) = |A|(|A|+1)/2

Question 10

idea of proof for theorem 3.12. max{|A+A|,|A.A|}≥1/8|A|⁵/⁴

Answer 10

• 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)

Question 11

A₁ and A₂ in proof of radons lemma

Answer 11

A₁={aᵢ: iϵP}

A₂={aⱼ: jϵN}

Question 12

P and N in proof of radons lemma

Answer 12

P={iϵ[d+2]:λᵢ>0}

N={jϵ[d+2]:λᵢ<0}

Question 13

Λ in proof of radons lemma

Answer 13

sum over all i in P of λᵢ = minus the sum over all j in N of λⱼ

Question 14

point that lies in the convex hulls of A₁ and A₂ proof of radons lemma

Answer 14

p = sum over i in P of λᵢ/Λ * aᵢ = sum over j in p of -λⱼ/Λ * aⱼ

Question 15

aim of radons lemma proof

Answer 15

define an A₁ and A₂ such that their convex hulls contain a common point

Question 16

set up of in proof of radons lemma

Answer 16

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

Question 17

Last part of Proof of Hellys Theorem

Answer 17

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ᵢ.

Question 18

Applying Radons Lemma in proof of Hellys Theorem

Answer 18

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.

Question 19

Set up in proof of Hellys Theorem.

Answer 19

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ⱼ.

Question 20

Main point in proof of caratheodorys theorem

Answer 20

Assume t is minimal. If t<=d+1 we are done. Then suppose for a contradiction t≥d+2.

Question 21

If t≥d+2 then in proof of caratheodorys theorem (middle part of proof)

Answer 21

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.

Question 22

Choose an α in proof of caratheodorys theorem

Answer 22

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

Question 23

Set up for proof of I(m,n)≤n √(m) + m.

Answer 23

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.

Question 24

(n choose 2) ≤

proof of I(m,n)≤n √(m) + m

Answer 24

(n choose 2) ≤ n²/2

Question 25

sum over all i in m of (dᵢ choose 2) ≥

proof of I(m,n)≤n √(m) + m

Answer 25

sum over all i in m of (dᵢ choose 2) ≥ 1/2 the sum over all i in m of (dᵢ-1)².

Question 26

Set up for proof of if n=4k³ I(n,n) ≥ (n⁴/³) / (³√4)

Answer 26

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²].

Question 27

lq and lq’ in proof that the number of triples spanning a triangle of unit area is at most 20n⁷/³.

Answer 27

the lines parallel to pq at distance 2/|p-q| from it.

Question 28

Lₚ =

in proof that the number of triples spanning a triangle of unit area is at most 20n⁷/³.

Answer 28

Lₚ = {lq, lq’: qϵP{p}}

Question 29

|Lₚ|

in proof that the number of triples spanning a triangle of unit area is at most 20n⁷/³.

Answer 29

2(n-1)

Question 30

#of unit triangles containing p = 
in proof that the number of triples spanning a triangle of unit area is at most 20n⁷/³.

Answer 30

of unit triangles containing p ≤ # of incidences of lq and lq’ = I (P{p}, Lₚ)

Question 31

To prove theorem: max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴

It suffices to show….

Answer 31

It suffices to show |A+A|,|A.A|≥1/64|A|⁵/²

Question 32

P in proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴

Answer 32

Let P=(A+A)x(A.A)⊆ℝ² so |P|=|A+A|x|A.A|

Question 33

L in proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴

Answer 33

Let L be the set of lines of the form x=a+t and y=a’t for a,a’ϵA.
So |L|=|A|²

Question 34

First part of proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴

Answer 34

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|³

Question 35

second part of proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴

Answer 35

Note, |L|=|A|²≤|P|.
So I(P,L)≤4(|P|²/³|L|²/³+|P|+|L|)≤12|P|²/³|L|²/³

Question 36

Set up for caratheodorys proof

Answer 36

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 λᵢ

Question 37

sum over i in [m] dᵢ choose 2 >=

proof of I(m,n)≤n √(m) + m

Answer 37

sum over i in [m] dᵢ choose 2 >= 1/2 sum over i in [m] (dᵢ-1) ²

Question 38

proof of I(m,n)≤n √(m) + m quick points

Answer 38

• 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

Question 39

I(P,L)= sum over i in [m] of dᵢ where dᵢ is

Answer 39

each point pᵢ has dᵢ incidences.

Question 40

There are at most _____ crossing pairs of lines in the plane.
(proof of I(m,n)≤n √(m) + m)

Answer 40

n choose 2

Question 41

A point pᵢ in P with dᵢ incidences gives rise to ____ crossing pairs of lines.
(proof of I(m,n)≤n √(m) + m)

Answer 41

dᵢ choose 2

Question 42

I(P,l)=

proof of if n=4k³ I(n,n) ≥ (n⁴/³) / (³√4)

Answer 42

k because l contains exactly k points of P, namely one for each x.

Question 43

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)

Answer 43

ak+b≤2k.2k+2k²=4k²

Question 44

For each line in L when t∈A then

proof of max{|A+A|,|A.A|} ≥ 1/8|A|⁵/⁴

Answer 44

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|³