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
V
Petr Hliněný,  FI MU Brno
FI: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. □
Up to symmetry, person A knows at least three others (out of five) - say B,C,D.
D
C
Then either some two of B,C,D known each other (and we have three!), or B,C,D are mutually strangers. □ □
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 ofp 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.
Petr Hliněný,  FI MU Brno
FI:MA010: Ramseý theory
B
Schur's theorem
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} is 2-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.. .
What is the colour of 3? It must be blue. However, what is then the colour of 5?
1, 2, 3, 4, 5c
1, 2, 3, 4, 5?
□
V
Petr Hliněný,  FI MU Brno
FI:MA010: Ramsey theory
Convex point configurations
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. c
Example 12.6. Among any 5 planar points in general position, some 4 form a convex quadrangle. c
This is an easy analysis, starting from the convex hull of all (a triangle).. .
s
S
s
□
V
Petr Hliněný,  FI MU Brno
FI:MA010: 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 S0 C S such that all the k-tuples of elements of S0 have the same colour (monochromatic S0).
Remark: For k = 1, this is the pigeon-hole principle. . . c
Proof: We use induction on k. The case of k = 1 is clear by the remark.
We now consider (k + 1)-tuples. Set Si = S, and x\ be the first element of S.
- Assign every k-tuple T of S1 \ {x1} the colour of T U By the inductive assumption, there exists an infinite monochromatic subsequence Si C S1 \{x1}.c
- Repeat the previous with S2 = S1, then with S3, S4, .. . ("till infinity") c
Finally, consider the above selected sequence S' = (x1? x2, x3,...). Every xj has its "own colour" (of the monochromatic subsequence Sj), and one colour repeats infinitely many times. This is our So. □
V
Petr Hliněný,  Fl MU Brno
FhMAOlO: Ramsey theory
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 M0 C M of n elements such that all the k-tuples of elements of M0 have the same colour (monochromatic M0).
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, I the following is true: In any collection of N(m, I) = (m„+^^) people, some m of them know each other or in some group of I they are mutually strangers. c
Proof by induction on m + I (a sketch): Notice that (cf. Pascal's triangle)
N(rn,Q=[   fn - fn - rn - ^= N(m - 1,£) + N(m,£ - 1) ,
Pick any person A. Then either at least N(m — 1,1) persons are known to A, or at least N(m,I — 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. □
Petr Hliněný,  FI MU Brno_6_FI: MA010: 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...) c
Proof: For c = 2, this is true by Example 12.1. We continue the proof by induction on c > 2; taking N1 = (c +1) • (N - 1) + 2 where N = N(c).
Pick any vertex a of KNl (whose edges are coloured with c + 1 colours). Then a has Ni — 1 = (c +1) • (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 KN. 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. c
Lastly, it remains to verify that N(c + 1) = |~(c + 1)! • e] = [c! • ej • (c + 1) +2, which follows from well-known e =    i=o      . D
Petr Hliněný,  Fl MU Brno_7_Fl: MA010: Ramsey theory
Graph Ramsey numbers
Definition: The Ramsey number R 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).
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: (u, 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. □
Petr Hlineny,  FI MU Brno_9_FI: MA010: Ramsey theory
12.3   Hales-Jewett theorem
Informal explanation: in high-dimensional tic-tac-toe game, there cannot be a draw.
Definition: Let n and D be integers A formal hypercube of dimension D and side n is the set of formal words XD = {1, 2,..., n}D.
A formal (combinatorial) line in XD is a word I G (X U {x})D \ XD where x is a (symbolic) variable. The n points of this line are the words l(x = 1),..., l(x = n). □
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.
Petr Hiineny,  FI MU Brn<
FI: MA010: 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'c) 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.
V
Petr Hiineny,  FI MU Brr
FI: MA010: Ramsey theory