Combinatorics - Chapter 3 defs and theorems

Question 1

convex set (def 1)

Answer 1

A set X⊆ℝᵈ is convex if for any points x₁,x₂ϵX and λϵ[0,1] then the point λx₁ +(1-λ)x₂ belongs to X.

Question 2

convex set (def 2)

Answer 2

A set X⊆ℝᵈ is convex if for any points x₁,x₂,..,xₙϵX and λ₁,…,λₙ ≥ 0 with the sum over i in [n] λᵢ = 1 then the point given by the sum over i in [n] λᵢxᵢ is in X

Question 3

convex hull (def 1)

Answer 3

The convex hull of a set X⊆ℝᵈ denoted conv(X) is the set of all convex combinations of all points in X.

Question 4

convex hull (def 2)

Answer 4

The convex hull of X is the intersection of all convex sets in ℝᵈ containing X

Question 5

Radons Lemma

Answer 5

Let A be a set of d+2 points in ℝᵈ. Then there exists two distinct subsets A₁,A₂⊆A such that conv(A₁)∩conv(A₂)≠Ø

Question 6

radon point of A

Answer 6

a point xϵconv(A₁)∩conv(A₂)

Question 7

radon partition

Answer 7

(A₁,A₂)

Question 8

hellys theorem

Answer 8

Let c₁,c₂,..,cₙ be convex sets in ℝᵈ and n≥d+1. Suppose that the intersection of every d+1 of these sets is no-empty then the intersection of all cᵢs is non-empty.

Question 9

caratheodorys theorem

Answer 9

Let X⊆ℝᵈ. Then each point xϵconv(X) is a convex combination of at most d+1 points of X

Question 10

incidence

Answer 10

let P be a set of m points and L a set of n lines in the plane. An incidence is a pair (p,l)ϵPxL such that p lies in l

Question 11

I(P,L)

Answer 11

the number of incidences for P and L

Question 12

I(m,n)

Answer 12

the maximum of I(P,L) over all choices of an m-element set P and an n-element set L.

Question 13

trivially, I(m,n)≤

Answer 13

I(m,n)≤ mn

Question 14

proposition 3.6. I(3,3).

Answer 14

I(3,3)=6.

Question 15

lemma 3.7. bound on I(m,n).

Answer 15

For all m,nϵℕ I(m,n)≤n √(m) + m

Question 16

cauchy schwarz inequality

Answer 16

(sum over i in [m] of xᵢyᵢ)² ≤ (sum over i in [m] of xᵢ²)(sum over i in [m] of yᵢ²)

Question 17

cauchy schwarz inequality for yᵢ=1

Answer 17

(sum over i in [m] of xᵢ)²≤ (sum over i in [m] of xᵢ²)m

Question 18

theorem 3.8. Szemeredi Trotter theorem

Answer 18

For all m,nϵℕ I(m,n)≤ 4 (m²/³n²/³+m+n)

Question 19

proposition 3.9. bound on szemeredi trotter is asymptotically tight for m=n=4k³

Answer 19

For n=4k³ I(n,n) ≥ (n⁴/³) / (³√4)

Question 20

corollary 3.10. Erdos and Purdy 1971.

Answer 20

For any set P of n points in the plane. The number of triples spanning a triangle of unit area is at most 20n⁷/³

Question 21

sum set

Answer 21

For any finite sets A,B⊆ℝ, A+B is the sum set defined as {a+b: aϵA, bϵB}.

Question 22

product set

Answer 22

For any finite sets A,B⊆ℝ, A.B is the product set defined as {a.b: aϵA, bϵB}.

Question 23

proposition 3.11. bound on sum and product sets.

Answer 23

Let A be a finite set in ℝ. Then, 2|A|-1 ≤ |A+A|,|A.A|≤ |A|(|A|+1)/2

Question 24

Theorem 3.12. Maximum of product and sum sets.

Answer 24

For any finite set A⊆ℝ, then max{|A+A|,|A.A|}≥1/8|A|⁵/⁴

Question 25

Drawing

Answer 25

A drawing of a graph G in the plane where the vertices of G are represented by definite points in the plane and every edge xyϵG is represented by a curve joining the two points corresponding to c and y.

Question 26

Crossing Number

Answer 26

The crossing number cr(G) of a graph is the smallest number of pairs of crossing edges in a drawing of G in the plane.

Question 27

Theorem 3.14. Lower bound on cr(G) (used in szemeredi proof)

Answer 27

Let G be a graph of |V(G)| vertices and |E(G)| edges. Then the crossing number of G is given by

cr(G)≥ |E(G)|³/64|V(G)|² - |V(G)|

Question 28

Theorem 3.15. Szemeredi Trotter Theorem for circles.

Answer 28

There exists a constant c such that I₁꜀ᵢᵣ꜀ₗₑ(m,n)≤c(m²/³n²/³+m+n) for all n,mϵℕ.