Combinatorics - Chapter 3 Flashcards
convex set informal
A set is convex is every element of the set can be expressed as a convex combination of elements from the set.
convex set visually
given points in X you can join the points with a line that wholly lies in X
convex hull informal
The convex hull is the polygon that contains all the points in X
Radons lemma is…
best possible
Hellys theorem informal
If the intersection of d+1 sets is non-empty then globally the intersection is non-empty.
The converse of hellys theorem….
holds
contrapositive form of hellys theorem
If the intersection of convex sets c₁,..,cₙ is empty then there exists cᵢ₁,cᵢ₂,…,cᵢₔ₊₁ with empty intersection.
hellys theorem is…
best possible
hellsys theorem doesn’t hold…
infinitely
caratheodorys theorem informal
We can write every point in the convex hull of X as a convex combination of up to d+1 points in X
caratheodorys theorem is…
best possible
How to show a theorem is best possible
give an example where it obtains its bounds
What do the constants in a convex combination sum to
1
incidence informal
If the point lies in a lines we say it is an incidence
n choose k is less than or equal to
2ⁿ
What two things to remember when calculating the sum and product sets.
- delete any repeat values
- remember to sum/times each element with itself.
order of lower bound on sum/product set
linear
order of upper bound on sum/product set
quadratic
The bound for 2|A|-1 ≤ |A+A|,|A.A|≤ |A|(|A|+1)/2 is…
tight (best possible)
set for show |A+A| attains the lower bound 2|A|-1
A = [n]
set for show |A+A| attains the upper bound |A|(|A|+1)/2
A = {2ᶦ: iϵℕ}
I₁꜀ᵢᵣ꜀ₗₑ(m,n)
Let I₁꜀ᵢᵣ꜀ₗₑ(m,n) denote the maximum possible number of indicies between m points and n unit circles in the plane.
