Combinatorics - Chapter 1

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

s₁,..,sₖ in pigeonhole principle

Answer 2

the sizes of each hole.

Question 3

1,…,n in pigeonhole principle

Answer 3

the pigeons

Question 4

c₁,…,cₖ in pigeonhole principle (colours)

Answer 4

the pigeonholes

Question 5

ramsey number

Answer 5

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 6

ramsey number informal

Answer 6

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

Question 7

R(t) =

Answer 7

R(t,t)

Question 8

How to show that R(s,t)=n

Answer 8

• 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

Question 9

R₁(s₁)=

Answer 9

s₁ because every colouring of Kₙ with one colour contains a monochromatic Kₛ₁ (if s₁<=n)

Question 10

R₂(s₁,s₂) =

Answer 10

R(s₁,s₂) (i.e. the original ramsey definition)

Question 11

R(3,3)=

Answer 11

6

Question 12

R(3,4)=

Answer 12

9

Question 13

R(3,5)=

Answer 13

14

Question 14

R(4,4)=

Answer 14

18

Question 15

R(4,5)=

Answer 15

25

Question 16

R(5,5)=

Answer 16

in the range 43-48

Question 17

How many ways are there to red/blue colour Kₙ

Answer 17

2^ (n choose 2) ways

Question 18

How many edges in a complete graph

Answer 18

n choose 2

Question 19

What is the bound for R(t)

Answer 19

( square root 2)ᵗ < R(t) ⩽ 4ᵗ

Question 20

R(Kₛ,Kₜ)=

Answer 20

R(s,t)

Question 21

Van der wearden numnber

Answer 21

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.

Question 22

n choose k

Answer 22

n! / k!(n-k)!

Question 23

binomial distrubution

Answer 23

(n choose x)(p)^x(1-p)^(n-x)

Question 24

erdos and szekeres

Answer 24

R(s,t)⩽R(s-1,t)+R(s,t-1)

Question 25

number of edges in a complete graph Kn

Answer 25

n choose 2 = n(n-1)/2

Question 26

pigeonhole principle simple

Answer 26

If at least n pigeons are placed into k pigeonholes then some hole contains at least the ceiling of n/k pigeons.

Question 27

First step when proving R(s,t)⩽(an expression)

Answer 27

let n=expression.

Question 28

How to show R(s,t)⩽n

Answer 28

Show any red/blue-edge-colouring of Kₙ contains a red Kₛ or a blue Kₜ.

Question 29

How to show R(s,t)≥n

Answer 29

Show R(s,t)>n-1. Find an explicit edge colouring without a red Kₛ or a blue Kₜ.

Question 30

(n choose t) is the number of ways….

Answer 30

to choose t vertices in Kₙ

Question 31

Expectation of X =

Answer 31

sum over i in natural numbers of i multiplied by the probability X=i

Question 32

colour blindness argument

Answer 32

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

Question 33

when to use a colour blindness argument

Answer 33

when showing inequalities of Ramsey numbers with different numbers of colours

Question 34

Erdos and Szekeres informal

Answer 34

R(s,t)⩽R(s-1,t)+R(s,t-1)

Question 35

Add probabilities if

Answer 35

one event or the other

Question 36

Multiply probabilities if

Answer 36

probabilities both events will happen

Question 37

Conditional probability

Answer 37

P(A|B)=P(A∩B)/P(B)

Question 38

Erdos Theorem Quick

Answer 38

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

Question 39

Schurs Theorem

Answer 39

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