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:

   Givenanyr,n,andμwecanfindanm0 suchthat,ifm≥m0 andther-com- binations 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 r- combinations of members of ∆n belong to the same Ci.

   1. (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.

   2. (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 ⌈ nk ⌉ 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:

   􏰏 • ify−x∈{1,2,4,8,9,13,15,16} C([x,y])= 􏰔 ify−x∈{3,5,6,7,10,11,12,14}.

   1. (a)  Prove that any K4 that contains the edge [0,1] is not C-monochromatic.
   2. (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.

   3. (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.

1

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

   C([x,y]) = 􏰔 or C([x,z]) = 􏰔 and conclude that K4 is not monochromatic.

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

1. Showthatx∈{3,5,6,7,10,11},y∈{5,6,7,10,11,12},andz∈{5,6,7,10,11,12,14}.
2. Show that if x ∈ {10, 11} then

   C([x, y]) = •. and conclude that K4 is not monochromatic.

3. Show that if x ∈ {3,5,6,7} and if
   C([x, y]) = C([x, z]) = 􏰔

then
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 C : N(3) → {•, 􏰔} be defined by

   􏰏• ifx|z−y C({x < y < z}) = 􏰔 otherwise.

   Find an infinite monochromatic set.

2

C([y,z]) = •

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:

W =···XY ··· XY ··· XY ··· XY …XY ··· XY ··· 􏰒􏰑􏰐􏰓 􏰒􏰑􏰐􏰓 􏰒􏰑􏰐􏰓 􏰒􏰑􏰐􏰓

mmm m

3