Combinatorics - Chapter 3

Question 1

convex set informal

Answer 1

A set is convex is every element of the set can be expressed as a convex combination of elements from the set.

Question 2

convex set visually

Answer 2

given points in X you can join the points with a line that wholly lies in X

Question 3

convex hull informal

Answer 3

The convex hull is the polygon that contains all the points in X

Question 4

Radons lemma is…

Answer 4

best possible

Question 5

Hellys theorem informal

Answer 5

If the intersection of d+1 sets is non-empty then globally the intersection is non-empty.

Question 6

The converse of hellys theorem….

Answer 6

holds

Question 7

contrapositive form of hellys theorem

Answer 7

If the intersection of convex sets c₁,..,cₙ is empty then there exists cᵢ₁,cᵢ₂,…,cᵢₔ₊₁ with empty intersection.

Question 8

hellys theorem is…

Answer 8

best possible

Question 9

hellsys theorem doesn’t hold…

Answer 9

infinitely

Question 10

caratheodorys theorem informal

Answer 10

We can write every point in the convex hull of X as a convex combination of up to d+1 points in X

Question 11

caratheodorys theorem is…

Answer 11

best possible

Question 12

How to show a theorem is best possible

Answer 12

give an example where it obtains its bounds

Question 13

What do the constants in a convex combination sum to

Answer 13

1

Question 14

incidence informal

Answer 14

If the point lies in a lines we say it is an incidence

Question 15

n choose k is less than or equal to

Answer 15

2ⁿ

Question 16

What two things to remember when calculating the sum and product sets.

Answer 16

• delete any repeat values

- remember to sum/times each element with itself.

Question 17

order of lower bound on sum/product set

Answer 17

linear

Question 18

order of upper bound on sum/product set

Answer 18

quadratic

Question 19

The bound for 2|A|-1 ≤ |A+A|,|A.A|≤ |A|(|A|+1)/2 is…

Answer 19

tight (best possible)

Question 20

set for show |A+A| attains the lower bound 2|A|-1

Answer 20

A = [n]

Question 21

set for show |A+A| attains the upper bound |A|(|A|+1)/2

Answer 21

A = {2ᶦ: iϵℕ}

Question 22

I₁꜀ᵢᵣ꜀ₗₑ(m,n)

Answer 22

Let I₁꜀ᵢᵣ꜀ₗₑ(m,n) denote the maximum possible number of indicies between m points and n unit circles in the plane.