Assignment 5 1. Let A = {1, 2, 3, 4, 5}. (a) Provide an example of a combinatorial line in Aб. (b) Provide an example of a 5-element subset of 46 that is not a combinatorial line. (c) Calculate the number of combinatorial lines in Aб. (d) Give an example of five focused combinatorial lines in A6. 2. Let A = {1,2,3} be an alphabet. Consider the 2-colouring of A³ depicted in the figure below. (1, 1, 3) (3,3,3) (3,3,2) (3,3,1) (3,2,1) (1, 1, 1) (2, 1, 1) (3, 1, 1) (a) Determine nine monochromatic 3-element sets of of collinear points in the cube A³. Does any of those sets correspond to a combinatorial line? (b) Based on your observation, what can you tell about the Hales-Jewett number H(2; 3)? 3. In this exercise you will prove that, for r ≥ 2, HJ(r; 2) = r, i.e., you will prove that for any 2- element alphabet A, any r ≥ 2, if n < r then there is an r-colouring of A" that does not yield any monochromatic combinatorial lines and if n ≥r then every r-colouring of A" that yields a monochromatic combinatorial line. Let r 2 and let A = {0, 1} be an alphabet. - (a) Suppose that n < r and consider the colouring c : A" → [0,r − 1] such that, for w = an Є An, c(w) |{i ≥ [1,n] : a¡ = 0}. Use the colouring c to establish that a1 a2 HJ (r; 2) ≥ r. = (b) Suppose that n ≥ r and that c is an r-colouring of the cube A". Prove that there are p and q, P < q, such that c(00 P 011 1) = c(00 011 n-p 9 n-q 1) and conclude that HJ (r; 2) = r. Carefully explain your reasoning. 4. Use the Hales-Jewett theorem to prove that for any prime number p and any 2-colouring of natural num- bers there is a 7-term arithmetic progression a1, a2, a3, A4, A5, A6, a7, not necessarily monochromatic, such that the set P = {pª¹, pª², pª³, pª4, pas, pª, pa7} is c-monochromatic. Note: Try to mimic the proof of van der Waerden's theorem that uses the Hales-Jewett theorem presented in the class. 5. In this exercise you will prove the following fact: Let S be a set of 1000 points in the plane II. If c is a 2-colouring of the plane then there is a c-monochromatic set S' similar to the set S. Here, two sets of points in the plane are similar if there is a composition of a homothety and a translation that maps one set onto the other. Fix c : II → {•, ■}, a 2-colouring of the plane. Let S = {A1, A2, . . ., A 1000} and let O = II be a fixed point. Let V = {OX : X = II} and let the 2-colouring c' of the set V be defined by c' (OX) = c(X). (a) Use the Hales-Jewett theorem to prove that there are a point Y = II and a real number λ such that the set {OY + 1 · OA : i = [1, 1000]} − V is c'-monochromatic. . Note: Take the set S = {OA; : i = [1, 1000]} to be the alphabet. Follow the same set of ideas you used in the previous exercise. (b) Determine a c-monochromatic set that is similar to S. 2