Ramsey Theory

　　“Complete disorder is impossible.”

　　A typical statement in Ramsey Theory is that “any colouring of a set S with finite number of colours contains a (structured) subset S′ where all its elements have the same colour”. One simple example of Ramsey Theory is the Pigeonholes principle. For n ∈ N, denote by [n] the set of {1, 2, . . . , n}.

　　Proposition 1.1 (Pigeonholes principle). Let k ∈ N and s1, . . . , sk be non-negative inte-gers. Let {1, 2, . . . , n} be coloured with colours c1, . . . , ck and n > si. Then there

　　exists i ∈ [k] such that there are at least si + 1 numbers of colour ci.

　　Proof. Suppose the contrary. For each i ∈ [k], there are at most si numbers of colour ci. Therefore, n ≤ s1 + s2 + · · · + sk, a contradiction. 

　　1.1 Ramsey numbers for complete graphs

　　Question. In a party of n people, does there always exists a group of 3 people that are all friends to each other or non of them are friends (i.e. strangers)?

　　If n is small, say n = 2, then it is impossible. If n is large, then this is likely to be true. What is the smallest n such that the question is yes? We now study this problem more formally.

　　Let Kn be the complete graph on n vertices, that is, V (Kn) = {x1, . . . , xn} and E(Kn) = {xixj : 1 ≤ i < j ≤ n}. An edge-colouring of Kn is an assignment of colours to each of it edges. (Sometime we say a colouring of edges of Kn instead.) A red/blue-edge-colouring of Kn is an edge-colouring of Kn using colours red and blue. It is monochromatic if all of its edges are coloured the same colour. We say a red Kn to mean a monochromatic copy of Kn where all its edges are coloured red.

　　Definition 1.2. For t ∈ N, the diagonal Ramsey number of t, denoted by R(t), is the smallest n ∈ N such that any red/blue-edge-colouring of Kn yields a monochromatic copy of Kt.

　　In our original question, let people be the vertices of a complete graph Kn. We colour the edge between two people red if they are friends and blue otherwise. So a group of

　　3 people that are all friends to each other corresponds to a red K3. Hence, our question translates to what is R(3)?Proposition 1.3. R(3) = R(3, 3) = 6.

　　Proof. First, we prove the lower bound by presenting a red/blue edge-colouring of K5 with no monochromatic triangles. Let 1, 2, 3, 4, 5 denote the vertices of K5. For every 1 ≤ i < j ≤ 5, colour the edge ij red if j − i ≡ ±1 (mod 5) and blue otherwise. It is easy to see that both the red graph and the blue graph form a cycle of length (number of edges) 5 and is thus triangle-free. We conclude that R(3, 3) > 5.

　　5Next, we prove the upper bound, that is, we will prove that in any red/blue edge-colouring of K6 there is a monochromatic triangle. Consider an arbitrary red/blue edge-colouring K6. Let x be an arbitrary vertex of K6. At least 3 of the edges incident with x are red or at least 3 are blue by the Pigeonholes principle (Proposition 1.1). Assume without loss of generality that there are at least 3 red edges incident with x (the complementary case, where there are at least 3 blue edges incident with x can be handled similarly). Let y1, y2, y3 be vertices of K6 such that xyi is red for i ∈ [3]. If the edge yiyj is red, then x, yi, yj form a red K3. Otherwise, y1y2, y1y3 and y2y3 are all blue and thus y1, y2, y3 form a blue K3. We conclude that, in either case, there is a monochromatic triangle and thus R(3, 3) ≤ 6.Definition 1.4. For s, t ∈ N, the Ramsey number of s and t, denoted by R(s, t), is the smallest n ∈ N such that any red/blue-edge-colouring of Kn yields a red copy of Ks or a blue copy of Kt.

　　So R(t) = R(t, t) for any t ∈ N. These numbers are named after the British mathemati-cian Frank Plumpton Ramsey. It is not a priori clear that Ramsey numbers are well-defined (that is, that they exist for every s, t ∈ N).Proof. We proceed by induction on s + t. If min{s, t} ≤ 2, then R(s, t) exists by Propo-sition 1.5. We can thus assume that s, t ≥ 3 and, in particular, s + t ≥ 6. It follows by the induction hypothesis that both R(s − 1, t) and R(s, t − 1) exist. Let p := R(s − 1, t), q := R(s, t − 1) and n := p + q.

　　Consider an arbitrary red/blue-edge-colouring of Kn. Let x be an arbitrary vertex of Kn. Since x is incident with n − 1 = (p − 1) + (q − 1) + 1 edges, each of which is coloured either red or blue, it follows by the Pigeonholes principle (Proposition 1.1) that there are at least p red edges or at least q blue edges which are incident with x. Assume without loss of generality that there are at least p red edges incident with x (the complementary case can be handled similarly). Let y1, . . . , yp be vertices of Kn such that xyi is red for every i ∈ [p]. Since p ≥ R(s − 1, t) and since every edge of {yiyj : 1 ≤ i < j ≤ p} is coloured either red or blue, it follows that this colouring yields either a red Ks−1 or a blue Kt. In the latter case we are done. In the former case, adding x to the red Ks−1 yields a red Ks. Proposition 1.8. For all t ∈ N, R(t) ≤ 22t−1 holds.

　　Proof. Let n = 22t−1. Fix some red/blue-edge-colouring of Kn. We will prove that this colouring must yield a monochromatic copy of Kt. Let x1 be an arbitrary vertex of Kn. There are n − 1 = 22t−2 + 22t−2 − 1 edges incident with x1. It follows that at least 22t−2 of these edges must be of the same colour (all red or all blue). Let N1 be an arbitrary set of 22t−2 vertices such that all edges of {x1v : v ∈ N1} have the same colour. Mark x1 with this colour (that is, if x1v is red for every v ∈ N1, then mark x1 red and otherwise mark it blue). Let x2 be an arbitrary vertex of N1. There are |N1| − 1 = 22t−3 + 22t−3 − 1 edges x2y, where y ∈ N1. It follows that at least 22t−3 of these edges must be of the same colour. Let N2 ⊆ N1 be an arbitrary set of 22t−3 vertices such that all edges of {x2v : v ∈ N2} have the same colour. Mark x2 with this colour. Repeating this process 2t − 1 times (this is possible since n = 22t−1 and we keep half the vertices in each step), we obtain a sequence of vertices x1, x2, . . . , x2t−1 such that(i) xi is marked either red or blue for every i ∈ [2t − 1], and

　　(ii) for every 1 ≤ i < j ≤ 2t − 1, the vertex xi is marked by the colour of the edge xixj .

　　It follows by (i) and by the pigeonhole principle that there exists a monochromatic (all red

　　or all blue) subsequence xi1 , xi2 , . . . , xit of x1, x2, . . . , x2t−1. It follows by (ii) that these vertices form a monochromatic copy of Kt. 

　　Note that the proof of Theorem 1.6 (and Corollary 1.7) requires Proposition 1.5, but the proof of Proposition 1.8 does not.1.2 Ramsey numbers for more than two colours

　　Definition 1.9. Let k, s1, . . . , sk ∈ N. The Ramsey Number of s1, . . . , sk, denoted by Rk(s1, . . . , sk), is the smallest n ∈ N such that for any edge-colouring of Kn with colours c1, . . . , ck, there exists some i ∈ [k] for which there exists a monochromatic copy of Ksi of colour ci.We will prove that these numbers are well-defined.Theorem 1.10. For all k, s1, . . . , sk ∈ N, Rk(s1, . . . , sk) exists.

　　Example 1.11. When colouring with only one colour, we clearly have R1(s1) = s1. Indeed, colouring Kn with one colour yields a monochromatic Kn which contains a monochromatic Ks1 if and only if n ≥ s1. When colouring with two colours we get the previously defined Ramsey number R(s1, s2) which is the same as R2(s1, s2) in the new notation. We already proved that these numbers exist.

　　Proof of Theorem 1.10. We proceed by induction on the number of colours k. As noted in Example 1.11, the assertion of the theorem holds for k ≤ 2. Assume that the assertion of the theorem holds for k − 1, that is, that Rk−1(t1, . . . , tk−1) exists for all t1, . . . , tk−1 ∈ N. Let s1, . . . , sk ∈ N be arbitrary, let m = Rk−1(s1, . . . , sk−1) and let n = R(m, sk). Note that m is well-defined by the induction hypothesis and that n is well-defined since the assertion of the theorem holds for k = 2. Consider an arbitrary edge-colouring c of Kn with colours c1, . . . , ck. Define a red/blue-edge-colouring c˜ of Kn by colouring an edge e blue if c(e) = ck and red otherwise. Since n ≥ R(m, sk), it follows that this colouring must yield a red Km or a blue Ksk . In the latter case, it follows by the definition of c˜ that the blue Ksk is monochromatic under c with colour ck. Similarly, in the former case the red Km are edge-coloured with colours c1, . . . , ck−1 under c. Since m ≥ Rk−1(s1, . . . , sk−1), it follows that there must exist some i ∈ [k − 1] for which there exists a copy of Ksi all of whose edges are coloured with the colour ci. 

　　Remark 1.12. This argument is sometime called ‘colour blindness’.

　　1.3 Small Ramsey numbers

　　The following table shows some known values of R(s, t). The ijth entry is the value of R(i, j) (if it is not known exactly, then the best current lower and upper bounds are given).

　　We conclude that, in either case, there is a red K3 or a blue K4 and thus R(3, 4) ≤ 9.

　　Next, we prove the lower bound by presenting a red/blue-edge-colouring of K8 with no red K3 and no blue K4. Let 1, 2, . . . , 8 denote the vertices of K8. For every 1 ≤ i < j ≤ 8, colour the edge ij blue if j − i ∈ {1, 2, 6, 7} and red otherwise. Assume for the sake of contradiction that there are vertices 1 ≤ x1 < x2 < x3 ≤ 8 which form a red K3. Since x1x2 is red, it follows by the definition of the colouring that x2 −x1 ≥ 3. Similarly, since x2x3 is red, it follows that x3 − x2 ≥ 3. Hence, x3 − x1 = (x3 − x2) + (x2 − x1) ≥ 6. It follows that x3 − x1 ∈ {6, 7} and thus x1x3 is blue contrary to our assumption. Assume then for the sake of contradiction that there are vertices 1 ≤ y1 < y2 < y3 < y4 ≤ 8 which form a blue K4. Clearly y4 − y1 ≥ 3. Since y1y4 is blue we conclude that y4 − y1 ∈ {6, 7} and therefore y1 ≤ 2 and y4 ≥ 7. Since y1y2 is blue it follows that y2 ≤ 4. Similarly, since y2y3 is blue it follows that y3 ≤ 6. However, y1y3 is blue as well and thus in fact y3 ≤ 4. It follows that y4 − y3 ≥ 3 and thus y3y4 is red (clearly y4 − y3 < 6 as y4 ≤ 8 and y3 ≥ 3) contrary to our assumption. We conclude that the given colouring yields no red K3 and no blue K4 entailing R(3, 4) > 8.

　　1.4 Lower bounds for Ramsey numbers

　　1.5 Ramsey Theory for graphs

　　Definition 1.16. For graphs G and H, the Ramsey number of G and H, denoted by R(G, H), is the smallest n ∈ N such that any red/blue-edge-colouring of Kn yields a red copy of G or a blue copy of H.

　　Similarly, we can define Ramsey number graphs G1, G2, . . . , Gk, Rk(G1, . . . , Gk). Note that R(s, t) = R(Ks, Kt) for s, t ∈ N.

　　Proposition 1.17. For graphs G and H, R(G, H) ≤ R(|V (G)|, |V (H)|).

　　Proof. Let s = |V (G)|, t = |V (H)| and n = R(s, t). Consider any red/blue-edge-colouring of Kn. By the definition of n, there must exist a red Ks or a blue Kt. In the former case, the red Ks contains a red G. Similarly, in the latter case, there exists a blue H. Hence R(G, H) ≤ n. 

　　Let ℓ ∈ N, let ℓK2 be the graph on 2ℓ vertices consisting of precisely ℓ disjoint edges. We sometime refer ℓK2 as a matching of size ℓ.

　　Theorem 1.18. For ℓ ≥ 1 and s ≥ 2, R(ℓK2, Ks) = 2ℓ + s − 2.

　　Proof. Consider a K2ℓ+s−3 with vertex set [2ℓ+s−3]. Colour the edge ij red if i, j ≤ 2ℓ−1, and blue otherwise. Note the graph induced by the red edges spans 2ℓ − 1 vertices, so it does not contain ℓK2 (which requires 2ℓ vertices). Let Kt be a complete graph in the subgraph induced by blue edges. Note that Kt contains at most one vertex in [2ℓ − 1]. Hence, we have t ≤ 2ℓ + s − 3 − (2ℓ − 2) = s − 1. Therefore R(ℓK2, Ks) > 2ℓ + s − 3.

　　Let n = 2ℓ + s − 2. Consider any red/blue-edge-coloured Kn. Let M be the largest red monochromatic matching. Suppose that M has size less than ℓ. So |V (M)| ≤ 2ℓ − 2. Note that there is no red edge with both vertices not in V (M) (or else we could make M bigger). Therefore the vertex set V (Kn) \ V (M) induces a blue complete graph and |V (Kn) \ V (M)| ≥ n − (2ℓ − 2) = s. Hence there exists a blue Ks or a red ℓK2. Thus R(ℓK2, Ks) = n. 

　　Theorem 1.19. For s ≥ t ≥ 1, R(sK2, tK2) = 2s + t − 1.

　　Proof. Consider a K2s+t−2 with vertex set [2s+t−2]. Colour the edge ij red if i, j ≤ 2s−1, and blue otherwise. Note the graph induced by the red edges spans 2s − 1 vertices, so it does not contain sK2 (which requires 2s vertices). Note that all blue edges must contain a vertex j > 2s − 1 and there are at most 2s + t − 2 − (2s − 1) = t − 1 such vertices. Hence there are at most t − 1 disjoint blue edges. Thus R(sK2, tK2) > 2s + t − 2.

　　We now show that R(sK2, tK2) ≤ 2s + t − 1. We proceed by induction on t. For t = 1, trivially (or by Theorem 1.18) R(sK2, K2) = 2s. We may assume that t ≥ 2. Suppose the contrary that R(sK2, tK2) > 2s + t − 1, that is, there exists a red/blue-edge-coloured K2s+t−1 without a red sK2 nor a blue tK2. Clearly there must some red edges and blue edges. Let x, y, z be vertices such that xy is red and yz is blue.

　　Remove the vertices x, y, z and called the resulting edge-coloured completed graph K. Note that

　　(2s + t − 1) − 3 = 2(s − 1) + (t − 1) − 1 = R((s − 1)K2, (t − 1)K2)

　　by the induction hypothesis. Hence K contains a red (s − 1)K2 or a blue (t − 1)K2. Therefore together with xy or yz, K2s+t−1 contains a red sK2 or a blue tK2, a contradiction. Therefore R(sK2, tK2) = 2s + t − 1. ✶✵