Combinatorics- Chapter 1 - Definitions And Theorems

Question 1

Pigeonhole Principle

Answer 1

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ᵢ.

Question 2

complete graph

Answer 2

Let Kₙ be the complete graph on n vertices, where every pair of vertices is joined by an edge.

Question 3

V(Kₙ)

Answer 3

the vertex set of Kₙ

Question 4

E(Kₙ)

Answer 4

the edge set of Kₙ

Question 5

edge-colouring

Answer 5

An edge-colouring on Kₙ is an assignment of colours to each edge of Kₙ

Question 6

edge-colouring as a function c

Answer 6

c: E(Kₙ)->{colours}

Question 7

monochromatic

Answer 7

A subgraph is monochromatic if all its edges are the same colour

Question 8

red H / blue H

Answer 8

a monochromatic copy of graph H whose edges are all red/blue respectively.

Question 9

ramsey number

Answer 9

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ₜ.

Question 10

proposition. R(3) = R(3,3) =

Answer 10

R(3) = R(3,3) = 6

Question 11

proposition. ramsey numbers for 1,2 swaps etc.

Answer 11

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

Question 12

Theorem. Erdos and Szekeves.

Answer 12

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)

Question 13

Corollary. R(s,t)⩽ a choose b

Answer 13

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).

Question 14

Proposition 1.7. R(s,t)⩽ 2^

Answer 14

For all s,t∈ℕ R(s,t)⩽2²ᵗ⁻¹

Question 15

ramsey number for k colours

Answer 15

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]

Question 16

Theorem. Existence of ramsey number for k colours.

Answer 16

For k,s₁,s₂,…,sₖ∈ℕ the ramsey number Rₖ(s₁,s₂,…,sₖ) exists.

Question 17

Proposition. R(3,4)

Answer 17

R(3,4)=9

Question 18

Theorem. Erdos.

Answer 18

Let t,n∈ℕ. If (n chose t) * 2^(1- (t choose 2))<1, then R(t)>n.

Question 19

Corollary. Lower bound for R(t) for t≥4

Answer 19

For t≥4, R(t)>⌊2^(t/2)⌋ holds.

Question 20

the ramsey numer of G and H where G and H are graphs

Answer 20

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.

Question 21

Proposition. ramsey numbers for graphs are welldefined.

Answer 21

For graphs G and H R(G,H)⩽R(|V(G)|,|V(H))

Question 22

Matching of size ℓ

Answer 22

Let ℓ∈ℕ. The matching of size ℓ is denoted ℓK₂ and is a graph on 2ℓ vertices consisting of precisely ℓ vertex disjoint edges.

Question 23

Theorem. R(ℓK₂, Kₜ).

Answer 23

For ℓ≥1 and t≥2, R(ℓK₂, Kₜ) = 2ℓ + t -2

Question 24

Theorem. R(sK₂, tK₂).

Answer 24

For s≥t≥1, R(sK₂, tK₂)=2s+t-1.

Question 25

Schurs Theorem

Answer 25

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

Question 26

Lemma. distinct real numbers contain an increasing/decreasing subsequence.

Answer 26

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

Question 27

Arithmetic Progression of length m (AP)

Answer 27

An Arithmetic Progression of length m is a sequence (a,a+d,a+2d,...,a+(m-1)d) for some a,d∈ℕ

Question 28

Van der waerden numnber

Answer 28

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.

Question 29

Theorem (Van der waerdens)

Answer 29

For any r,m∈ℕ W(r,m) exists

Question 30

Focus

Answer 30

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]

Question 31

R(t)=R(t,t)⩽(2t-2 t-1)

Answer 31

R(t,t)⩽(2t-2 t-1)<2²ᵗ⁻²

Question 32

The ramsey number of graphs G₁,..,Gₖ

Answer 32

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ᵢ