MATH301 - Assignment 2 - Solved

1.    Write a short essay (300-400 words) on the life and work of Bartel Leendert van der Waerden.

2.    Prove the following statement: Suppose that nine people are gathered at a dinner party. Then there is a group of four people at the party who are all mutual acquaintances or there is a group of three people at the party who are all mutual strangers.

3.    Recall the statement of Ramsey’s theorem:

Given any r, n, and µ we can find an m0 such that, if m ≥ m0 and the r- combinations of any Γm are divided in any manner into µ mutually exclusive classes Ci (i = 1,2,...,µ), then Γm must contain a sub-class ∆n such that all the rcombinations of members of ∆n belong to the same Ci.

(a)   By choosing appropriate values of r, n, and µ show that the Generalized Pigeonhole

Principle:

Suppose you have k pigeonholes and n pigeons to be placed in them. If n > k then at least one pigeonhole contains at least two pigeons.

is a special case of Ramsey’s theorem.

(b)   By choosing appropriate values of r, n, and µ show that the Pigeonhole Principle:

If n pigeons are sitting in k pigeonholes, where n > k, then there is at least one pigeonhole with at least   pigeons.

is a special case of Ramsey’s theorem.

4.    In this problem you will show that there is a 2-colouring of K17 with no monochromatic K4.

Label each vertex of K17 by one of the integers 0,1,2,...,16.

Let [x,y] denote the edge between the vertices x,y ∈ {0,1,2,...,16} with x < y.

We define a 2-colouring of the edges of K17 in the following way:

 •               if y − x ∈ {1,2,4,8,9,13,15,16}  if y − x ∈ {3,5,6,7,10,11,12,14}.

(a)   Prove that any K4 that contains the edge [0,1] is not C-monochromatic. (b) Prove that for any x,y ∈ {0,1,2,...,16}, x < y,

C([x,y]) = C([0,y − x]).

Explain why this fact implies that to check if K4 with vertices x,y,z,w, x < y < z < w, is monochromatic, it is enough to check if K4 with vertices 0,y − x,z − x,w − x is monochromatic.

(c) Recall that you have established that if K4 contains the edge [0,1] then it cannot be C-monochromatic.

So, let us consider the complete graph K4 with the vertices 0,x,y,z, 2 ≤ x < y < z.

i.       Suppose that C([0,x]) = C([0,y]) = C([0,z]) = •. We will show that, under these conditions, K4 is not C-monochromatic.

A.     Show that x ∈ {2,4,8,9,13}, y ∈ {4,8,9,13,15} and z ∈ {8,9,13,15,16} .

B.     Show that if x ∈ {2,9,13} then

C([x,y]) =  or C([x,z]) =

and conclude that K4 is not monochromatic.

C.      Show that if x ∈ {4,8} and if

C([x,y]) = C([x,z]) = •

then

C(y,z) =

and conclude that K4 is not monochromatic.

ii.     Suppose that C([0,x]) = C([0,y]) = C([0,z]) = . We will show that, under these conditions, K4 is not C-monochromatic.

A.     Show that x ∈ {3,5,6,7,10,11}, y ∈ {5,6,7,10,11,12}, and z ∈ {5,6,7,10,11,12,14}.

B.     Show that if x ∈ {10,11} then

C([x,y]) = •.

and conclude that K4 is not monochromatic.

C.      Show that if x ∈ {3,5,6,7} and if

C([x,y]) = C([x,z]) =

then

C([y,z]) = •

and conclude that K4 is not monochromatic.

5.    In the previous exercise we have established that there is a 2-colouring of K17 with no monochromatic K4. Does this contradict the fact that R(4,3) = R(3,4) = 9? Why yes, or why not?

6.    Prove that you need at least 18 people at a dinner party (including you) to make sure that there is a group of four people at the party who are all mutual acquaintances or there is a group of four people at the party who are all mutual strangers.

7.    Recall that for r ∈ N and any set X we define X(r) to be the set of all subsets on X with exactly r elements:

X(r) = {A ⊂ X : |A| = r}.

Also, recall that Ramsey’s theorem guarantees that whenever N(r) is 2-coloured, there exists an infinite monochromatic set.

Let the colouring be defined by

                                                                                                                •       if x|z − y

 otherwise.

Find an infinite monochromatic set.

8.    Consider an infinite word W on the alphabet {A,B,C}.

This means that W is an infinite sequence of the letters from the set {A,B,C}.

For example,

A = ABBCCCCB ···BA···AC ···CAA···

is an infinite word on the alphabet {A,B,C}.

In this exercise we consider ANY infinite word W that uses letters A, B, and C.

Prove that there is a 2-word XY on the alphabet {A,B,C} that will appear in W at least 1000 times in a way that 999 words that separate consecutive appearances of XY are of the same length: