Ramsey Theory

Question 1

For every 2-colouring of the edges of K_6 there is…

Answer 1

A monochromatic triangle (every edge has the same colour in the subgraph triangle)

Question 2

State Ramsey’s Theorem

Answer 2

For every integer r \geq 2 there is an integer n such that for every 2-colouring of the edges of K_n, there is a monochromatic K_r

Question 3

When is a graph or subgraph monochromatic?

Answer 3

When every edge has the same colour.

Question 4

What is the 6-people at a party theorem?

Answer 4

At least 3 people know each other or do not know each other in a 6 person party.

Question 5

Give the upper and lower bound conditions for Ramsey numbers so that R(s,t)=n

Answer 5

R(s,t) \leq n if every red-blue edge colouring of K_n has a monochromatic K_s or K_t. R(s,t) \geq n (alternatively R(s,t) > n-1) if there exists a red-blue colouring of a graph on n-1 vertices that does not contain both a monochromatic K_s and K_t.

Question 6

State Erdos and Szekeres’ version of Ramsey’s Theorem

Answer 6

For every integers s,t \geq 1 there is a least positive integer R(r,s) such that every red-blue edge colouring of the complete graph on R(r,s) vertices contains a blue of clique on r vertices or a red clique on s vertices.

Question 7

Erdos and Szekeres’ Lemma: If R(r-1,s) and R(r,s-1) exist then ___ exists. In particular ___ \leq ___ + ___

Answer 7

R(r,s)… R(r,s) \leq R(r-1,s) + R(r,s-1)

Question 8

R(4) =

Answer 8

18

Question 9

R(r,s) \leq ___

Answer 9

(r+s-2) choose (r-1)

Question 10

Erdos 1947 Theorem: For every integer r \geq 3 there is an edge-2-coloured complete graph on n = ___ vertices with no monochromatic ___

Answer 10

floor(r^{r/2})… K_r

Question 11

Campos, Griffiths, Morris and Sahasrabudhe’s Theorem:

Answer 11

R(r) \leq 3.9921875^r

Question 12

Erdos and Szekeres’s Theorem for multicoloured graphs: For integers k \geq 2 and r_1, r_2, …, r_k \geq 1 there is a least positive integer R(r_2, …, r_k) such that every edge colouring of the complete graph on R(r_2, …, r_k) vertices with colours 1, 2, …, k there is a ___ ___ ___ ___ all of whose edge are coloured ___.

Answer 12

clique on r_i vertices… i

Question 13

Infinite Schur’s Theorem: For any partition of N into a finite number of parts, some part contains three integers x, y and z with ___ = ___

Answer 13

x+y = z

Question 14

Finite Schur;s Theorem: For every k in N there exists a minimum number S(k), called Schur’s number, such that for every partition of {1, 2, …, S(k)} into k parts, some parts contain integers x, y and z with ___ = ___

Answer 14

x+y = z

Question 15

R(r) \leq ___

Answer 15

2^{2r-2}

Question 16

What is f(r) as in the happy end problem?

Answer 16

f(r) is the minimum integer such that every set of f(r) points in the plane, with no three points collinear, contains r points that form a convex r-gon.

Question 17

For every integer r there is an integer n such that every set of at least n points in the plane, with no three collinear points, contains r points the form a ___ ___

Answer 17

convex r-gon