Assignment 2 Due on Friday, February 2, 2024, at 10:00pm 1. Write a short essay (300-400 words) on the life and work of Bartel Leendert van der Waerden. 2. Generalize

the proof of the fact that R(3, 3) = 6 to establish the fact that, for k ≥ 3, R(3, 3, . . ., 3) ≤ k(R(3, 3, . . ., 3) – 1) + 2. k k-1 3. The Ramsey number R(m, m) is the smallest natural number N such that, in any edge 2-colouring of the complete graph Ky, there is guaranteed to be a monochromatic copy of Km. Prove that R(m, m) ≤ 22m-3 Note: This result means that at a party with 22m-3 people there must be a group of m people that mutually know each other or that mutually do not know each other. But we cannot tell if the same is true if there are 22m-3 - 1 people at the party. 4. Use Ramsey's theorem on any other way to prove the following: For any n, k € N there is m = m(n, k) € N such that there are A1, A2,..., Ak C [1, m] = {1, 2, . . ., m} with the following properties: (a) |A₁| = n, for all i = [1, k]; (b) For any i, j = [1, k], if i ‡ j then |A; ^ Aj| = p for some (the same) p = [0, n]. In other words, for any n, k € N we can find an interval [1, m] that contains k subsets of the size n such that their pairwise intersections are of the same size. 5. (a) Prove that if there are 18 people at a dinner party (including you) then 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. (b) Based on one of the previous problems in this assignment, what is the size of a party that would guarantee a group of five people at the party who are all mutual acquaintances or theta there is a group of five people at the party who are all mutual strangers. 6. Let x : N → {1,2, ..., r} be an r-colouring of positive integers and let k € N\{1}. Use van der Waerden's theorem to prove that there is a x-monochromatic k-term arithmetic progression with an even common difference. 7. Consider an infinite word W on the alphabet {A, B}. This means that W is an infinite sequence of the letters A and B. For example, A = ABBBBAAB BA……. AA. BBA... ... is an infinite word on the alphabet {A, B}. In this exercise we consider ANY infinite word W that uses letters A and B, and C. Prove that there is a 3-word XYZ on the alphabet {A, B} that will appear in W 500 times in a way that 499 words that separate consecutive appearances of XYZ are of the same length that is divisible by 6: W = ... XYZ Clues for HW2 #4: 6m XYZ 6m If you can answer "what are the nodes, XYZ What is k? K=4 how big the monochromatic diagram gets 6m Clues for HW4: The question should read Start the answer for question 4), start with this "given m and n, consider every subset of {1,2...,m} with n elements." XYZ...XYZ In homework 4, m is number of talent, n is size of subsets. Here n is 2, the number of skills each players get The number of common integers = the number of common skills in example 6) from tutorial 2 6m fill in from tutorial pages XYZ...