Section 6: Ramsey Theory

Question 1

Ramsey’s theorem

Answer 1

For all s, t ≥ 2, there is a natural number n such that every colouring of the edges of Kn with red and blue contains either a copy of Ks with all edges red or a copy of Kt with all edges blue.

Question 2

Ramsey number

Answer 2

for any positive integers s, t ≥ 2, R(s, t) is the smallest natural number n such that every colouring of the edges of Kn with red and blue contains either a copy of Ks with all edges red or a copy of Kt with all edges blue

Question 3

Ramsey’s theorem restated

Answer 3

For all s, t ≥ 2, there is a natural number n such that every graph G with n vertices either contains a copy of Ks or has an independent set with t vertices.

Question 4

For any positive integer t ≥ 2, we have R(2,t)=

Answer 4

t

Question 5

Erdös and Szekeres theorem

Answer 5

R(s, t) is finite for all integers s, t ≥ 2. Moreover, for s, t ≥ 3,
R(s, t) ≤ R(s, t − 1) + R(s − 1, t).

Question 6

R(3,4)=

Answer 6

9