12 Introduction to Ramsey Theory Informally saying, Ramsey theory is a theory of numerous results in different areas of discrete mathematics, all basically showing that "a complete disorder is mathematically impossible". In other words, Ramsey theory is looking for order inside disorder. We very briefly introduce some fundamental directions of research of this interesting branch of mathematics. Brief outline of this lecture • Exempl. problems: the party problem, Schur's theorem, convex points • Ramsey theorem: its infinite version, and some special finite bounds • Hales-Jewett theorem - another kind of problems ■ Hlinený. Fl Ml hl: MA010: Ramsey theory 12.1 Some exemplary problems Example 12.1. Consider six people meeting at a party Then three of them know each other, or three of them are mutually strangers, c Up to symmetry, person A knows at least three others (out of five) - say B,C,D. D * B Then either some two of B,C,D known each other (and we have three!), or B,C,D are mutually strangers, c D Theorem 12.2. (the Party theorem) For every integer p there exists N such that: In any group of N people, some p of them know each other or in some group of p they are mutually strangers. Remark. Imagine that the pairs of people of the group are coloured blue if they know each other, or red if they are strangers (do not know each other). Then Theorem 12.2 claims that there exists a monochromatic k-tuple. etr Hlinený, Fl MU Br Fl: MAOIO: Ramsey theon Theorem 12.3. For any integer c > 0 there exists N such that the following holds: If the set of integers from 1 to N is coloured arbitrarily with c colours, then the equation x + y = z has a monochromatic solution in this set. c Example 12.4. If the set {1,2, 3, 4, 5} is2-coloured, then the equation x + y = z has a monochromatic solution there (Theorem 12.3 for c = 2 and N = 5). Up to symmetry, number 1 is red and then 2 is blue, hence 4 is red.. . 1,2,3,4,5c What is the colour of 3? It must be blue. However, what is then the colour of 5? 1,2,3,4, 5? D etr Hliněný, Fl MU_____________________________________________________I: MAOIO: Ramsey theory Theorem 12.5. For any integer q > 3 there exists N such that the following holds: If N points in the plane are in an arbitrary general position (i.e. no three of them are colinear), then there exist q of them which form the vertices of a convex q-gon. a Example 12.6. Among any 5 planar points in general position, some 4 form a convex quadrangle, a This is an easy analysis, starting from the convex hull of all (a triangle).. . ® ,■* D etr Hliněný, Fl MU_____________________________________________________I: MAOIO: Ramsey theory 12.2 Theorem(s) of Ramsey Theorem 12.7. (Ramsey theorem - infinite) For any integers c and k the following holds: If each of the k-tuples of elements of an infinite sequence S is coloured with one of c colours, then there exists an infinite subsequence So CS such that all the k-tuples of elements of S o have the same colour (monochromatic So). Remark: For k = 1, this is the pigeon-hole principle. . . Proof: We use induction on k. The case of k = 1 is clear by the remark. We now consider (k + l)-tuples. Set S\ = S, and x\ be the first element of S. - Assign every fc-tuple T of S\ \ {x\} the colour of T U {x\}. By the inductive assumption, there exists an infinite monochromatic subsequence S[ C S'i\{xi}.ö - Repeat the previous with S*2 = S[, then with 6*3, 6*4, .. . ("till infinity") c Finally, consider the above selected sequence S' = (xi,X2,#3,...). Every Xj has its "own colour" (of the monochromatic subsequence S^), and one colour repeats infinitely many times. This is our Sq. □ etr Hliněný, Fl MU Brno 5 Fl: MAOIO: Ramsey theon Theorem 12.8. (Ramsey theorem) For any integers c, k and n, there exists N = R(k; c) such that the following holds: If each of the k-tuples of elements of an N-element set M is coloured with one of c colours, then there exists a subset Mq C M of n elements such that all the k-tuples of elements of Mq have the same colour (monochromatic Mq). This theorem follows from Theorem 12.7 via a usual compactness argument. However, this approach gives no usable bounds on R(k; c), c Lemma 12.9. (Theorem 12.2) For every integers m, £ the following is true: In any collection ofN(m,£) = (m„^2) people, some m of them know each other or in some group of £ they are mutually strangers, c Proof by induction on m + £ (a sketch): Notice that (cf. Pascal's triangle) N(m,t)=[ = + )= N(rn-!,£) +N(rn,£-1).o rn — 1 J V to — 2 / V to — 1 Pick any person A. Then either at least N(m — l,£) persons are known to A, or at least N(m,£ — 1) persons are strangers to A. In either case, by induction, we get a solution of the respective subproblem, and possibly add A to it. D Petr Hliněný, Fl MU Brno 6 Fl: MAOIO: Ramsey theory Edge-coloured graph view Ramsey-type results for coloured pairs (k = 2) are often formulated for edge-coloured (not proper colourings, though!) graphs. Such as the Party problem (Theorem 12.2) asks for a monochromatic copy of Kp. Or, the following is well-known: Lemma 12.10. For any c > 1 the following holds: If the edges of a complete graph Kn where N = N (c) = \c\ ■ e] are coloured with c colours, then there exists a monochromatic triangle. (Here e = 2.718281...) Proof: For c = 2, this is true by Example 12.1. We continue the proof by induction on c > 2; taking Nľ = (c + 1) • (N - 1) + 2 where N = N (c). Pick any vertex a of Kn1 (whose edges are coloured with c+ 1 colours). Then a has A?i —1 = (c+l)-(N —1) + 1 incident edges, and at least N of them, by the pigeon-hole principle, have the same colour - say 1. The subgraph induced on the other ends of these edges is a copy K' of K^. So, either some edge of this K' has colour 1 and we get a triangle in this colour with a, or K' is edge-c-coloured, and the statement folows by induction. _ Lastly, it remains to verify that N(c+ 1) = f(c+ 1)! • e] = [c\ • ej • (c+1) +2, which follows from well-known e = YllZo V*' ■ c etr Hliněný, Fl MU Brno 7 Fl: MAOIO: Ramsey theon Graph Ramsey numbers Definition: The Ramsey number i?( Kp, Kq, Kr,... ) is the minimum integer R such v-----------------v-----------------' C that the following is true: Whenever the edges of the complete graph Kr are coloured arbitrarily with c colours, then there exists a monochromatic copy of Kp in colour 1, or of Kq in colour 2, or of Kr in colour 3, or .... This Ramsey number is always defined by Theorem 12.8, and the definition can be extended to arbitrary subgraphs instead of the cliques. For instance, N(c) = R{K3,K3,...) from Lemma 12.10 are tight for c = 2,3 (N= 6, 17). etr Hlinený, Fl MU Br Fl: MAOIO: Ramsey theon Corollary 12.11. (Theorem 12.3) For any integer c > 0 the following holds: If the set of integers from 1 to N(c) = \c\ ■ e] is coloured arbitrarily with c colours, then the equation x + y = z has a monochromatic solution in this set. c Proof: We colour the edges of the complete graph Kn on vertices {1, ...,N} as follows: {w, v} gets the colour of the number \u — v\. Then a monochromatic triangle exists by Lemma 12.10 - say on the vertices a < b < c - and hence the numbers x = b — a, y = c — b, and z = c — a have the same colour and x + y = z. ü >etr Hliněný, Fl MU Br FhMAOlO: Ramsey theory 12.3 Hales-Jewett theorem Informal explanation: in high-dimensional tic-tac-toe game, there cannot be a draw. o o O Definition: Let n and D be integers A formal hypercube of dimension D and side n is the set of formal words TiD = {1,2,..., n}D. A formal (combinatorial) line in TiD is a word i G (E U {x})D \ Y*D where x is a (symbolic) variable. The n points of this line are the words £(x = 1),..., £(x = n), c Remark: Every formal line is a line in the "usual sense", but not the converse. Hence the coming statement is actually much stronger than just saying that a high-dimensional tic-tac-toe game has no draw. Theorem 12.12. (Hales-Jewett) For every integers n, c > 1 there exists D = D(n, c) such that the following holds: If the points of a formal D-dimensional hypercube of side n are coloured with c colours, then there always exists a monochromatic combinatorial line. etr Hlinený, Fl MU Bri MAOIO: Ramsey theory Van der Waerden's theorem Theorem 12.13. (van der Waerden) For every integers n, c > 1 there exists W = W(n, c) such that the following holds: If the integers 1,2,... ,W are coloured with c colours, then there exists a monochromatic arithmetic progression among them, c Proof : We choose W = nD^n^ where D is from Theorem 12.12. The integers 1,2,... ,W, written down as n-adic numbers, then form a hypercube of side n and dimension D(n,c). A monochromatic line exists in this hypercube by Theorem 12.12, and the points of this line clearly give an arithmetic progression of length n. etr Hliněný, Fl MU Brno 11 Fl: MAOIO: Ramsey theory