Combinatorics - Chapter 1 Flashcards
pigeonhole principle
Let k∈ℕ be the number of colours and s₁,..,sₖ be non -ve integers . Let [n] be coloured with colours c₁,…,cₖ and n> the sum of the sᵢs. Then there exists iϵ[k] s.t. there are at least sᵢ+1 numbers with colour cᵢ.
s₁,..,sₖ in pigeonhole principle
the sizes of each hole.
1,…,n in pigeonhole principle
the pigeons
c₁,…,cₖ in pigeonhole principle (colours)
the pigeonholes
ramsey number
For s,t∈ℕ the ramsey number of s and t denoted by R(s,t) is the smallest n s.t. every red/blue-edge-colouring of Kₙ contains a red Kₛ or a blue Kₜ.
ramsey number informal
the smallest n s.t. no matter how you colour the edges of Kₙ with red and blue you can always find a red Kₛ or a blue Kₜ.
R(t) =
R(t,t)
How to show that R(s,t)=n
- LOWER BOUND show R(s,t)>n-1 via an explicit counter example
- UPPER BOUND show Kₙ contains a red Kₛ or a blue Kₜ
- upper and lower bound together makes R(s,t)=n
R₁(s₁)=
s₁ because every colouring of Kₙ with one colour contains a monochromatic Kₛ₁ (if s₁<=n)
R₂(s₁,s₂) =
R(s₁,s₂) (i.e. the original ramsey definition)
R(3,3)=
6
R(3,4)=
9
R(3,5)=
14
R(4,4)=
18
R(4,5)=
25
R(5,5)=
in the range 43-48
How many ways are there to red/blue colour Kₙ
2^ (n choose 2) ways
How many edges in a complete graph
n choose 2
What is the bound for R(t)
( square root 2)ᵗ < R(t) ⩽ 4ᵗ
R(Kₛ,Kₜ)=
R(s,t)
Van der wearden numnber
For any r,m∈ℕ the van der weerden number of r and m denoted by W(r,m) is the smallest n such that whenever [n] is coloured with r colours, then there exists a monochromatic arithmetic progression of length m.
n choose k
n! / k!(n-k)!
binomial distrubution
(n choose x)(p)^x(1-p)^(n-x)
erdos and szekeres
R(s,t)⩽R(s-1,t)+R(s,t-1)
number of edges in a complete graph Kn
n choose 2 = n(n-1)/2
pigeonhole principle simple
If at least n pigeons are placed into k pigeonholes then some hole contains at least the ceiling of n/k pigeons.
First step when proving R(s,t)⩽(an expression)
let n=expression.
How to show R(s,t)⩽n
Show any red/blue-edge-colouring of Kₙ contains a red Kₛ or a blue Kₜ.
How to show R(s,t)≥n
Show R(s,t)>n-1. Find an explicit edge colouring without a red Kₛ or a blue Kₜ.
(n choose t) is the number of ways….
to choose t vertices in Kₙ
Expectation of X =
sum over i in natural numbers of i multiplied by the probability X=i
colour blindness argument
- Define the colouring with the bigger amount of colours
- From this colouring define another colouring on a smaller amount of colours where you colour with a certain colour if it was coloured with a group of colours in the original colouring.
- Apply Ramsey definition and look as cases.
when to use a colour blindness argument
when showing inequalities of Ramsey numbers with different numbers of colours
Erdos and Szekeres informal
R(s,t)⩽R(s-1,t)+R(s,t-1)
Add probabilities if
one event or the other
Multiply probabilities if
probabilities both events will happen
Conditional probability
P(A|B)=P(A∩B)/P(B)
Erdos Theorem Quick
Let t,n∈ℕ. If (n chose t) * 2^(1- (t choose 2))<1, then R(t)>n.
Schurs Theorem
For k∈ℕ there exists n=n(k)∈ℕ such that every k colouring of [n] there exists integers x,y,z∈ℕ all coloured with the same colour s.t. x+y=z
