Combinatorics- Chapter 1 - Definitions And Theorems 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ᵢ.
complete graph
Let Kₙ be the complete graph on n vertices, where every pair of vertices is joined by an edge.
V(Kₙ)
the vertex set of Kₙ
E(Kₙ)
the edge set of Kₙ
edge-colouring
An edge-colouring on Kₙ is an assignment of colours to each edge of Kₙ
edge-colouring as a function c
c: E(Kₙ)->{colours}
monochromatic
A subgraph is monochromatic if all its edges are the same colour
red H / blue H
a monochromatic copy of graph H whose edges are all red/blue respectively.
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ₜ.
proposition. R(3) = R(3,3) =
R(3) = R(3,3) = 6
proposition. ramsey numbers for 1,2 swaps etc.
For all s,t∈ℕ
1) R(1,t)=1
(2) R(2,t)=t
(3) If R(s,t) exists, then R(t,s)=R(s,t
Theorem. Erdos and Szekeves.
For all s,t∈ℕ R(s,t) exists. Moreover, If s,t≥2 then R(s,t)⩽R(s-1,t)+R(s,t-1)
Corollary. R(s,t)⩽ a choose b
For all s,t∈ℕ R(s,t)⩽(s+t-2 s-1).
In particular R(t)=R(t,t)⩽(2t-2 t-1)<2²ᵗ⁻². (just sub in t for s).
Proposition 1.7. R(s,t)⩽ 2^
For all s,t∈ℕ R(s,t)⩽2²ᵗ⁻¹
ramsey number for k colours
Let k,s₁,s₂,…,sₖ∈ℕ . The ramsey number of s₁,s₂,…,sₖ denoted Rₖ is the smallest integer n∈ℕ s.t. every edge colouring of Kₙ with colours c₁,c₂,..,cₖ contains a monochromatic copy of Kₛᵢ with colour cᵢ for some i∈[k]
Theorem. Existence of ramsey number for k colours.
For k,s₁,s₂,…,sₖ∈ℕ the ramsey number Rₖ(s₁,s₂,…,sₖ) exists.
Proposition. R(3,4)
R(3,4)=9
Theorem. Erdos.
Let t,n∈ℕ. If (n chose t) * 2^(1- (t choose 2))<1, then R(t)>n.
Corollary. Lower bound for R(t) for t≥4
For t≥4, R(t)>⌊2^(t/2)⌋ holds.
the ramsey numer of G and H where G and H are graphs
For graphs G and H, the ramsey number of G and H denoted by R(G,H) is the smallest n∈ℕ s.t. any red/blue-edge-colouring of Kₙ contains a red copy of G or a blue copy of H.
Proposition. ramsey numbers for graphs are welldefined.
For graphs G and H R(G,H)⩽R(|V(G)|,|V(H))
Matching of size ℓ
Let ℓ∈ℕ. The matching of size ℓ is denoted ℓK₂ and is a graph on 2ℓ vertices consisting of precisely ℓ vertex disjoint edges.
Theorem. R(ℓK₂, Kₜ).
For ℓ≥1 and t≥2, R(ℓK₂, Kₜ) = 2ℓ + t -2
Theorem. R(sK₂, tK₂).
For s≥t≥1, R(sK₂, tK₂)=2s+t-1.
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
Lemma. distinct real numbers contain an increasing/decreasing subsequence.
For s,t∈ℕ any sequence of distinct real numbers a₁,a₂,..,aₙ with n>st contains an increasing subsequence of length s+1 or decreasing subsequence of length t+1
Arithmetic Progression of length m (AP)
An Arithmetic Progression of length m is a sequence (a,a+d,a+2d,…,a+(m-1)d) for some a,d∈ℕ
Van der waerden numnber
For any r,m∈ℕ the van der waerden 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.
Theorem (Van der waerdens)
For any r,m∈ℕ W(r,m) exists
Focus
Let A₁,A₂,..,Aₖ each be an AP of length m where Aᵢ=(aᵢ, aᵢ+dᵢ, aᵢ+2dᵢ, … , aᵢ + (m-1)dᵢ). We say that A₁,…,Aₖ are focussed at f if f=aᵢ + md for all i∈[k]
R(t)=R(t,t)⩽(2t-2 t-1)
R(t,t)⩽(2t-2 t-1)<2²ᵗ⁻²
The ramsey number of graphs G₁,..,Gₖ
the ramsey numer of G₁,..,Gₖ denoted Rₖ(G₁,..,Gₖ) is the smallest n∈ℕ s.t. any k-edge-colouring of Kₙ with colours c₁,..,cₖ contains a monochromatic copy of Gᵢ coloured with colour cᵢ
