lie I 8 Ramsey Numbers Author: John G. Michaels, Department of Mathematics, State University ol New York, College at Brockport. Prerequisites: The prerequisites for this chapter are the pigeonhole principle and basic concepts of graphs. See, for example, Sections 4.2, 7.2 and 7.3 of Discrete Mathematics and Its Applications, Second Edition, by Kenneth II. Rosen. Suppose there are 6 people at a party, where each pair of people are either friends or strangers. We can show that there must be either 3 mutual friends or 3 mutual strangers at the party. To do this, we set up a graph G with 6 vertices (corresponding to the 6 people), where edges represent friendships. We need to show that there must be a triangle (i.e., a simple circuit of length 3) in G or else a triangle in G, the complement of G. This problem can be rephrased as the following edge-coloring problem: Show that if every edge of A'6 is colored red or green, then there must be either a red triangle or a green triangle. To see that these two problems are equivalent, take G to be the subgraph of Kg consisting of the 6 vertices and the red edges; therefore G consists of the 6 vertices and the green edges. A red II i in l\,, corresponds to n i ..I I niiiiiiiil I......In iii (,', whereas a green ||i< corresponds to a set of 3 mutual ni iminer* I In |• i<>»>(' thai there is either a red or a green triangle in A'6 is a simple i|ilu ni.......f the pigeonhole principle Itegin l.y choosing a vertex i> in K$. I. i i In edges on v represent pigeons and the colors red and green be the i| I wo pigeonholes. Since d(v) — 5 and each edge on v is either red or n ■ have 5 pigeons and 2 pigeonholes. Therefore some pigeonhole holds at I.....i I pigeons; that is, there are at least 3 red edges or 3 green edges incident mm i' Assuming that v has at least 3 red edges, say {v,a},{v,b}, and {v,c}, ............ the edges joining a, 6, c. If any of these 3 edges is red, we obtain a i .....igle. If none of the 3 edges is red, then we have a green triangle joining I, ft, i l A similar argument works if v has at least 3 green edges.) Thus, we are inteed of obtaining a monochromatic triangle, that is, a triangle such that all II.n edges are of the same color. In this chapter we extend these ideas further, examining questions such m I he following. What is the minimum number of people needed at a party III order to guarantee that there are at least 4 mutual friends or 4 mutual .......,i is? What is the minimum number needed to guarantee that there are 3 mutual friends or 5 mutual strangers? What is the minimum number needed In guarantee that there are 4 mutual close friends, 7 mutual acquaintances who .......t close friends, or 9 mutual strangers? The minimum numbers in problems such as these are called Ramsey num-lii i , named after Frank Ramsey*, who in 1930 published a paper [8] on set theory that generalized the pigeonhole principle. Ramsey Numbers Ah we saw earlier, no matter how the edges of A6 are colored red or green, Kg Contains a subgraph A'3 all edges of which are colored red or a subgraph A'3 nil edges of which are colored green. That is, Kg contains either a red A'3 or n green A3. We say that the integer 6 has the (3, 3)-Ramsey property. More generally, we have the following definition. Definition 1 Let i and j be integers such that i > 2 and j > 2. A positive integer m has the (i,j)-Ramsey property if A'm contains either a red A', or a green Kj as a subgraph, no matter how the edges of A'm are colored red or green. □ * See Discrete Mathematics and 7ts Applications, Second Edition, for biographical information on Ramsey. 138 140 Ampliation:, ol /!;•., niln M.tthunuili, ly Ntinih, 141 From the above discussion, we know that (. linn • I ■ • (II, I) li uiis< y properly But is 6 the smallest such number? Suppose we take A., .ui.l ". ol.»r" il.s lOedgei using Is and 2s, as in Figure la. There are no monochromatic triangles in either Figure lb or lc. Therefore this coloring shows that 5 does not have the (3,3)-Ramsey property. It is easy to see that no positive integer smaller than 5 has the (3,3)-Ramsey property. (See Exercise 3.) Therefore, 6 is the smallest integer with this property, and is called a Ramsey number. 1 1 (a) (b) Figure 1. A coloring of K5. (c) Definition 2 The Ramsey number R(i,j) is the smallest positive integer that has the (7,.;')-Ramsey property. m For example, i?(3,3) = 6, since 6 has the (3,3)-Ramsey property but no smaller positive integer has this property. Example 1 Find R(2,7), the smallest positive integer that has the (2,7)-Ramsey property. Solution: We begin by examining the positive integers n such that every coloring of the edges of Kn with red and green results in either a red A'2 (i.e., a red edge) or a green A7. The number R(2,7) is the smallest positive integer with this property. Consider any coloring of the edges of A7. Either there is at least one red edge, or else every edge is colored green. If there is a red edge, then we have the desired red A'2. If every edge was colored green, then we have the desired green A'7. Thus 7 has the (2,7)-Ramsey property, which says that R(2,7) < 7. But R(2,7) ^ 7. To see this, consider the coloring of A'6 where each edge is colored red. Then K$ has neither a red A'2 nor a green A'7, and so 6 does not have the (2, 7)-Ramsey property. Therefore R(2,7) = 7. □ I In1 .11 j'.umi'iil, in llir above example i mi l>< neiienili/.ed by replacing 7 with lliy integer k > '2 to obtain: /Y(2, k) k. i I l.i is left as Kxercise -1.) This example also leads us to make four other (tlmervations: 1 I'or all integers i > 2 and j > 2, R(i,j) = R(j,i). 2 If in has the (7, j)-Ramsey property, then so does every integer n > m. 8, If »7i does not have the (i,j)-Ramsey property, then neither does any lllleger 71 < ra. 4. If ii > «2, then R(h,j) > R(i2,j)-I'.....Is of these four facts are left to the reader as Exercises 5-8. Note that when we try to find R{i,j), we are looking for a red A'; or I green Kj\ that is, "red" is associated with the variable i and "green" is iiNHociated with the variable j. Likewise, when we try to find R(j,i), "red" is associated with j and "green" with i. Since R(i,j) = R(j, i), we need only look 1.1 a monochromatic A; subgraph or a monochromatic A'j subgraph. The definition of the Ramsey number R(i,j) requires us to find the smallest positive integer with the (i, j)-Ramsey property. But suppose that for some 1 and j there is no positive integer with the (i, j)-Ramsey property? In such a I ase there would be no Ramsey number R(i,j). This leads us to the question: Tor every choice of positive integers i > 2 and j > 2, is there a Ramsey num-ber R(i,j)? The following lemma and theorem provide an affirmative answer to this question. Lemma 1 If »' > 3 and j > 3, then R(hj)J)- (1) Proof: Let m — R(i,j — 1) + R(i — 1, j). We will show that m has the Ramsey property. Suppose the edges of Km have been colored red or green and v is a vertex of Km. Partition the vertex set V into 2 subsets: A = all vertices adjacent to v along a red edge B = all vertices adjacent to v along a green edge. Since \A\ + \B\ = \A U B\ = m - 1 = R(i,j - 1) + #(* - U) - 1, either L4| > R(i - 1, j) or \B\ > R(iJ - !)• If this were not the case, we would have L4| < R(i - U) and \B\ < R(i,j - 1), which would imply that \A U B\< R(i - 1, j) + R(hJ - 1) = m - 1. 143 Ampliation', til lh\t iiiUi M.ilhiiin.lln n This would contradict the fact that |,4 U H\ m I Consider the case where \A\ > R(i — Now ...nil. i the complete subgraph on the vertices in A. This is a subgraph of/\'m, which we call K\m, We will show that K\a\ contains either a red A',- or a green Kj. Since \A\ > R(i — K\a\ has either a red A',_i or a green Kj. If we have a red A,_i, wo add the red edges joining v to the vertices of A,_i to obtain a red K%. Thus, K\a\> and hence Km, has either a red A",- or a green Kj. This says that m has the (i, j)-Ramsey property. (The case where |5| > R(i,j — 1) is left as Exercise 9.) Therefore, inequality (1) has been proved. □ This lemma establishes a relationship that Ramsey numbers must satisfy. The following theorem uses mathematical induction together with this relationship to prove the existence of the Ramsey numbers. Theorem 1 Ramsey's Theorem If i and j are integers (i > 2 and j > 2), then there is a positive integer with the (i,j)-Ramsey property (and hence R(i,j) exists). Proof: We use (1) and the Principle of Mathematical Induction to prove that for all integers i > 2 and j > 2 there is a positive integer with the (i, j)-Ramsey property. Let P(n) be the statement: P(n): If i + j = n, then there is an integer with the (i, j)-Ramsey property. The base case is P(4), since the smallest values of i and j under consideration are i = j = 2. We know from the comments following Example 1 that there is an integer with the (2,2)-Ramsey property. Therefore P(4) is true. Now we assume that P(n) is true and show that P(n + 1) is also true. Assume that i + j = n + 1. Therefore i + (j — 1) = n and (i — 1) + j = n. P(n) states that there are integers with the — 1)-Ramsey property and the (i— l,j)-Ramsey property. Hence the Ramsey numbers R(i,j — 1) and R(i — exist. Inequality (1) guarantees that R(i,j) must also exist. Therefore P(n + 1) is also true. The Principle of Mathematical Induction guarantees that P{n) is true for all i > 2 and j > 2. This shows that R{i,j) exists if i > 2 and j > 2. ■ So far we know the values of the following Ramsey numbers: R{2,k) = R(k,2) = k i?(3,3) = 6. If i > 2 and j > 2, it rapidly becomes very difficult to find R(i,j) because of the large number of possible edge colorings of the graphs Kn. Hence, it is no unpriNc that Ihf lis! (if K.'iiiini'v iiiiiiiIxtm whom- rxw't valine are known is very limit We will now evaluate Home of thrm\ Ixample2 Find /(■(:{, I) Solution: From Lemma 1 we know that i?(3,4) < 72(3,3) + R{2,4) = 6 + 4 = 10. I.. i letermine if i?(3,4) < 10, we might consider looking at all possible red/green colorings of the edges of Kg. If one of these colorings has no red A3 or green A4, can conclude that i?(3,4) = 10. However, if every red/green coloring of A9 produces either a red A3 or a green A'4, we must then look at colorings of A8, etc. Examining all possible red/green colorings of the edges of A9 is not an rimy task—A9 has 36 edges, so initially there would be 236 * 69,000,000,000 .. .lorings to examine. Fortunately, we can avoid examining the colorings of A9, because of the following fact: If i > 3, j > 3, and if R(i,j — 1) and R(i — are even, then R(i,j) < R(i,j - 1) + R(i - l,j) - 1. (2) The proof of this fact follows the proof of Lemma 1, and is left as Exercise 10. Using (2) with i = 3 and j — 4 yields fl(3,4) < 7?(3,3) + 7?(2,4)- 1 =6+4-1 = 9 and we therefore know that i?(3,4) < 9. To see that 8 does not have the (3,4)-Ramsey property, consider the coloring of the graph K%, where the red edges are drawn in Figure 2(a) and the green edges in Figure 2(b). It is easy to see that there is no triangle in 2(a). In Exercise 11 the reader is asked to check that there is no A4 in 2(b). Thus, i?(3,4) = 9. □ Example 3 Find #(3,5). Solution: From (1) we know that fl(3,5) < tf(3,4) +J?(2,5) = 9 + 5 = 14 Ari'i«.,i,<,r. „in,-.....„. AtlH (b) A coloring of In fact, 72(3,5) = 14. To see this, we show that 13 does not have the (3,5)-Ramsey property. Draw K13 with vertices labeled 1,2,..., 13. Color the edge red if \i - j\ = 1, 5, 8 or 12, and color the edge green otherwise. We leave it to the reader to verify in Exercise 12 that this graph has no red K3 or green K5. □ The re are a few other Ramsey numbers whose values are known exactly. Table 1 lists these numbers and ranges for some of the smaller Ramsey numbers. For example, 72(5,4) = 72(4,5) is known to be 25, 26, or 27. Table 1. Ramsey Numbers R(i,j). From the remark following Example 1, we know exact values of all Ramsey numbers R(i,j) when i — 2oi j = 2. Aside from these, only eight other Ramsey numbers have known values. The Ramsey numbers 72(3,3), 72(4,3), 72(5,3), and 72(4,4) were found in 1955 by A. M. Gleason and R. E. Greenwood; 72(6,3) was found by J. G. Kalbfleisch in 1966; 72(7,3) was found by J. E. Graver and J. Yackel in 1968; 72(8,3) was found recently by B. McKay and Z. Ke Min; 72(9,3) was found by C. M. Grinstead and S. M. Roberts in 1982. Itiimmiy Numborn 145 Mimy upper anil lower I>ouii 2 and j > 2, then < C{% + j - 2,i - 1). PfOOf: A proof by induction can be given here, following closely the induction given for Theorem 1. This is left as Exercise 14. ■ It is also known that if k > 2, then 2*/2 < R(k,k) < 22*"3, and if j > 13, iIm ii /i'(.'i,j) < C(j,2) — 5. Proofs of these facts can be found in Tomescu [10]. Generalizations I he Ramsey numbers discussed in the last section represent only one family of It.niisey numbers. In this section we will briefly study some other families of these numbers. For example, suppose we take K„ and color its edges red, yellow, or green. What is the smallest positive integer n that guarantees that K„ has a subgraph i hat. is a red K3, a yellow K3, or a green K3? We might also think of this problem in terms of friendships rather than colors. A group of n countries each send a diplomat to a meeting. Each pair of countries are friendly toward each other, neutral toward each other, or enemies of each other. What is the minimum number of countries that need to be represented at the meeting in order to guarantee that among the countries represented there will be 3 mutual friends, 3 mutually neutral ones, or 3 mutual enemies? The minimum such number is written 72(3,3,3;2). The "2" is written as part of 72(3,3, 3; 2) because edges (i.e., the objects being colored) are determined by 2 vertices. (As we shall see, the 2 can be replaced by a larger positive integer.) The three 3s can be replaced by any number of positive integers to obtain other families of Ramsey numbers. For example, using the 3 colors red, yellow, and green, 72(5,4,7; 2) is the smallest positive integer n with the property that if the edges of K„ are colored with the 3 colors, then Kn contains a red Ks, a yellow Ki, or a green K7. Definition 3 Suppose ti,*'a, ■ ■ ■ ,in are positive integers, where each ij > 2. A positive integer m has the (h, ..., in; 2)-Ramsey property if, given n colors 1,2,... ,n, Km has a subgraph K{. of color j, for some j, no matter how the edges of Km are colored with the n colors. The smallest positive integer with the (ii,..., i„;2)-Ramsey property is called the Ramsey number 72(i;,..., in; 2). □ 146 AppllC.ltHHIS III />/•.( fdfíl M.lf/ll>/M.lfl Note that if n = 2, the Ramsey numbers H(ix , ij,'.') an the Hainsey mini bers /?(«!, 12) studied in the previous section. Again we are faced with the question: Do these numbers always exist? Thill is, for a given list i,-,... ,in, are there positive integers with the (i,,..., i„;'.') Ramsey property so that there is a smallest one (i.e., the Ramsey numbi 1 R(U,..., in; 2))? The answer is yes, and a proof using the Principle of Mai he matical Induction can be found in Graham, Rothschild, and Spencer [6]. Very little is also known about the numbers 72(z'i,..., i„; 2) if n > 3. However, if ij = 2 for all j, then 72(2,...,2;2) = 2. This is left as Exercise 15. If each ij > 3, the only Ramsey number whose value is known is i2(3,3,3; 2). Example 4 Show that 72(3,3,3; 2) = 17. Solution: Consider any coloring of the edges of K~n, using the colors red, yellow, and green. Choose any vertex v. Of the 16 edges incident on v, there is a single color that appears on at least 6 of them, by the Pigeonhole Principle. Suppose this color is red, and that there are 6 red edges joining v to vertices labeled 1,2,3,4,5,6. If one of the edges joining i and j (1 < i < 6, 1 < j < 6) is also red, then we have a red A'3. Otherwise, every one of the edges joining i and j is yellow or green. These edges give a graph colored with 2 colors, and we know that such a graph has a monochromatic A'3 (yellow or green) since 72(3,3) = 6. This says that A'17 must have a A3 that is red, yellow, or green. Therefore 72(3,3,3; 2) < 17. To see that 71(3,3,3; 2) > 17, consult Berge [1, opposite p.420] for a coloring of A'i6 with 3 colors that has no monochromatic triangle. □ So far we have dealt with Ramsey numbers of the form 72(t'i,... ,i„;2) by looking at them from the standpoint of coloring the edges of the graph Km with n colors and looking for monochromatic subgraphs Ki-. But there is another way to develop these numbers and further generalize ideas. Consider the problem in the Introduction—the problem of finding a red or green subgraph A'3 in Kg. Start with K& and its vertex set V. Take all 2-element subsets of V (i.e., the edges of K$) and divide these subsets into 2 collections C\ and C2. The number 6 has the (3,3)-Ramsey property if and only if: (i) There is a 3-element subset of V with all its 2-element subsets in C\, or (ii) There is a 3-element subset of V with all its 2-element subsets in Ci- 1 /i(i|i|i» ii lliiiwwy Mmi/xv. 147 I limit my, of ( as the Net of edgf* colored led ami ( iim the Net of edges color'''' 11, we see that we have 11 red triangle il and 2 nil each ij > r. A positive integer m has the (i\,..., in\r)-Ramsey property II 1 In' following statement is true: If S is a set of size m and the r-element subsets of 5 are partitioned into n collections C\, ■ ■ ■ ,Cn, then for some j there is a subset of 5 of size ij such that each of its r-element subsets belong to Cj. The Ramsey number 7?,(ii,..., in; r) is the smallest positive integer that has 1 lir (?'i,..., in\ r)-Ramsey property. D In particular, when r — 2, we can think of this definition in terms °f Coloring the edges of Km with n colors and taking Cj as the set of edges of color j. The numbers ij give the number of vertices in the monochromatic Kij subgraphs. We mention without proof Ramsey's Theorem regarding the existence of these Ramsey numbers. A proof can be found in Graham, Rothschild, and Spencer [6]. Theorem 3 Ramsey's Theorem If »'1,..., i„, r are positive integers where n > 2 and each ij > r, the Ramsey number 7ř(i'i, ...,»'„;r) exists. ' Earlier in this chapter we displayed the known Ramsey numbers of the form 7ř(ii,z'2;2). We also proved that 72(3,3,3;2) = 17. If r > 3, very little is known about exact values of the Ramsey numbers. See Exercise 17 for an example of one type of Ramsey number whose exact value is known. If r = 1, the Ramsey numbers R{i\,..., i„; 1) are easy to find, since in this case we need only consider the 1-element subsets of S. The following theorem gives a formula for these numbers. 148 Application:, at Dit.t into M.illiain.ili, •. Theorem 4 R(iu...in;l) = it + (n-1). Proof: Let i'i + ... + in — (n — 1) = m. We first show that the Integer m has the (t'j,..., i„; 1)-Ramsey property. Take a set 5 of size m and divide its 1-element subsets into n classes Ci,...,Cn. Observe that there must be a subscript jo such that \Cj0\ > ij0. (If \Cj \ < ij for all /, then \Cj\ < ij - 1. Therefore m = \Ci\ + ... + \Cn\ < (j'i — 1) + ... + («„ — 1) = i\ + • • • + in — n = m — 1, and hence m < m — 1, which is a contradiction.) If we take any ij0 elements of Cj0, we have a subset of 5 of size ij0 that has all its 1-element subsets belonging to Cj0. This shows that R(ii ,...,i„;l) < t'i +----\- in - (n - 1). We now show that m — 1 = ii H-----h in — n does not have the ,..., in; 1)- Ramsey property. Take a set 5 where |5| = »! + ••• + in — n. Partition its 1 - element subsets into n classes Ci,... ,Cn where \Cj \ = ij — 1. With this partition there is no subset of 5 of size ij that has all its 1-element subsets belonging to Cj. Note the particular case of this theorem when »'i R(2.....2;l) = n + l. = in = 2: This fact shows how Ramsey theory can be thought of as a generalization of the pigeonhole principle. In the terminology of Ramsey numbers, the fact that R(2,..., 2; 1) = n + 1 means that n + 1 is the smallest positive integer with the property that if 5 has size n +1 and the subsets of S are partitioned into n sets Ci,..., Cn, then for some j there is a subset of S of size 2 such that each of its elements belong to Cj. Hence, some Cj has at least 2 elements. If we think of a set S of n + 1 pigeons and the subset Cj, (j = 1,..., n) as the set of pigeons roosting in pigeonhole j, then some pigeonhole must have at least 2 pigeons in it. Thus, the Ramsey numbers R(2,..., 2; 1) give the smallest number of pigeons that force at least 2 to roost in the same pigeonhole. / t.im-.ny Ntnnhi'r- 149 Mini Q m (1,8}| we have a red tolul..... 2 + 2 ■ A. Also, if R = {2,5} and (/ { I, ;t,'I}, we have a green Hnliitiiiii I I it A. However, if S = {1, , :t, ^1}, we are not guaranteed a monochromatic solu- i..... To sec this, take Ii - {1,-1} and G = {2,3}. The equation x + y = z is ii' •! sal islied for any choices of j\ //, .: ( It or for any choices of x,y, z £ G. I In- number 5 can be looked on as a "dividing point" here. If n > 5, then partitioning {1,n} into red and green sets will always result in a monochro-iM .1 ic solution to x + y = z, whereas if n < 5, we may fail to have a monochro-iii.il.ic solution. We write 5(2) = 5, Where the number 2 indicates the fact that we are using 2 colors. The letter is used in honor of I. Schur*, who in 1916 developed this material while i mlying a problem related to Fermat's Last Theorem (xn + yn = z" has no Integer solutions if n > 2). Rather than work with only 2 colors, we can color {1,2, ...,n} with k < olors and look for the minimum value of n, written S(k), that guarantees a monochromatic solution to x + y = z. If k = 1, it is easy to see that 5(1) =2. (If {1, 2} is colored with 1 color, then we have the solution 1 + 1 = 2; the smaller wet {1} yields no solution to x + y = z.) If k = 3, it is known that 5(3) = 14. That is, no matter how the integers in the set {1,..., 14} are colored with 3 colors, x + y = z will have a monochromatic solution. It is natural to ask the question: For each positive integer k, is there a number S(k)? For example if we wish to use 4 colors, is there a positive integer 5(4) such that any coloring of {1,..., 5(4)} with 4 colors will give a monochromatic solution? The following theorem shows that the numbers S(k) always exist and are bounded above by the family of Ramsey numbers i?(3,..., 3; 2)- Schur's Theorem Suppose the integers 1,2,3,4,5 are each colored red or green. That is, suppose 5 = {1,2,3,4,5} is partitioned into 2 subsets, R and G, where the integers in R are colored red and the integers in G are colored green. Then it is known that the equation x + y = z has a monochromatic solution. (See Exercise 18.) That is, the equation x+y = z is satisfied for some x, y, z £ R or some x, y, z £ G. For example, if R = {2,4,5} Theorem 5 If k is a positive integer, then S(k) < /?(3,...,3;2) (where there are k 3s in the notation for the Ramsey number). * Issai Schur (1875-1941) was a Russian mathematician who attended schools in Latvia and Germany. Most of his teaching career was spent at the University of Berlin-Forced into retirement by the Nazis in 1935, he eventually emigrated to Palestine where he died two years later. He contributed to many areas of mathematics, and is best known for his work in the area of abstract algebra called the representation theory of groups. 150 Ampliation:, of /)/■„ mlii M.ilhimi.ili, n Proof: We will show that if the Integtn 1,3.....R(3, ,3;2) arc colored with k colors, then the equation x + y — z will have........i< h I.....natic solution (This implies that S(k) < fl(3,...,3;2) since S(k) is the Hiiiallest integer with the monochromatic solution property.) Let n = 72(3,..., 3; 2) and color the integers 1,2,..., n with k colors. Thll gives a partition of 1,2,..., n into k sets, Si, 52,..., St, where integers in thn same set have the same color. Now take the graph K„, label its vertices 1,2, ...,n, and label its edgoi according to the following rule: edge {i, j} has label \i — j\ This labeling has a special feature: every triangle has two sides with labels whose sum is equal to the label on the third side. (To see this, suppose we havt . a triangle determined by j'i,»2,»3, and assume ii > i2 > t'3. The 3 edge labels are ii - i2, i2 - »3, and i'i - »3) and we have (n - i2) + (i2 - »3) = (»i - 13). We will use these labels to color the edges of Kn: use color m on edge {i, j} if its label \i — j\ £ Sm. This gives a coloring of Kn with the k colors used for the elements in the sets Sj.....Sj.. Since n = R(3,..., 3; 2), n has the (3,..., 3; 2)-Ramsey property, and so there must be a monochromatic triangle in a'n. If its 3 vertices are j'i, i2,i3, and if we let x = i\ — i2, y = i2 — 13, and z — z'i — {3, then we have x + y = z where all 3 values have the same color. ■ Note that the theorem shows only the existence of S(k), by showing that those numbers are bounded above by certain Ramsey numbers. For example, if k = 3, the theorem states that 5(3) < JJ(3,3,3;2) = 17. Therefore, we know that x + y = z has a monochromatic solution, no matter how the integers 1,..., 17 are colored with 3 colors. But the theorem does not give the value of the minimum number with this property, S(3), which is known to be 14. It is natural to ask what happens if we have more than 3 variables in the equation. For an extension to equations of the form xi + ... + xn-\ = x„, see Beutelspacher and Brestovansky [2]. Convex Sets - civet no,"0" We7m Sh°W h°W RamS6y nUmberS Pla^ a roIe » constructing lZ*P1tg0n:- A TVGX POlyg°n 18 a Pol^on P such ^at if x and y are points » the mterior of P, then the line segment joining , and y lies complete y :n\ Ntitnhot: 151 l„.„|, /■ In Figure 3 the lirxiW>» (« K"") '« wl,rr",lH ,l,<.' ^"ulrilateral , .....n,v, (,.,, .....■ -............. «•!««• IHeg.nent jouung , and y , . |,l„, exterior of (.lie I K«'m Figure 3. Two polygons. [f we take n(> 3) points in the plane, no 3 of which are collinear, we can i iys connect then to form an n-gon. But can we guarantee that the n-gon will be convex? (The answer is no, even for 4 points, as shown by the 4-gon in Figure 3.) But suppose we do not select all n points? For example, given 5 pi lints, no 3 of which are collinear, can we always find 4 of the 5 points so that u hen they are connected we obtain a 4-gon that is convex? Then answer is yes, nn.I is left to the reader as Exercise 19. In general, suppose we want to guarantee that we can obtain a convex mi gon by connecting m of n given points, no 3 of which are collinear. Is there iluays an integer n that guarantees a convex m-gon, and, if so, how large must n be? For example, if we want a convex 5-gon, how many points, n, .....st we start with in order to guarantee that we can obtain a convex 5-gon? The following theorem, proved by Erdos and Szekeres [3] in 1935, shows that Itainsey numbers can be used to find a solution. In fact, it was this paper 1 hat provided the impetus for the study of Ramsey numbers and suggested the possibility of its wide applicability in mathematics. Theorem 6 Suppose m is a positive integer and there are n given points, no 3 of which are collinear. If n > R(m,5;4), then a convex m-gon can be obtained from m of the n points. Proof: Suppose n > R(m, 5; 4) and 5 is a set of n points in the plane, with no 3 points collinear. Since n has the (m,5;4)-Ramsey property, no matter how we divide the 4-element subsets of S into 2 collections C\ and C2, either (i) There is a subset of S of size m with all its 4-element subsets in C\, or (ii) There is a subset of S of size 5 with all its 4-element subsets in C2. We will take C\ to be the collection of all subsets of S of size 4 where the 4-gon determined by the points is convex and take C2 to be the collection of all subsets of S of size 4 where the 4-gons are concave. But note that alternative (ii) cannot happen. That is, it is impossible Aptiln .mom. (.//),..„ ,,,/„ Mitthonui ,iy NiiiiiIhiih to have 5 points in tlx- plane that give rinc mily I......icnv« I gnus. (TIiih I Exercise 19.) Therefore, we are guaranteed <>! having • > niilmrl ,4 C .S' wher = m and all 4-gons determined by A are convex We will now show that the m points of A determine a convex rn-gon. I,el k be the largest positive integer such that k of the m points form a convex fc-gon, Suppose G is a convex m-gon determined by k of the points of A. If k • m then at least one of the elements of A, say ai, lies inside the convex k-gow <. Therefore there are 3 vertices of G, say 02,03,04, such that aj lies inside thi triangle determined by these vertices. Hence, the set {01,02,03,04} detennim a concave 4-gon, contradicting the property of A that all its 4-gons are convex Therefore k -ft m, and we must have k = m. This says that the m points of I determine the desired convex m-gon. The Ramsey number R{m, 5; 4) in Theorem 7 gives a set of values for „ that guarantee he existence of a convex m-gon. But it remains an unsolved problem to find the smallest integer x (which depends on m) such that if n >" then a convex m-gon can be obtained from m of the n points Graph Ramsey Numbers So far, we have examined colorings of Am and looked for monochromatic A,-subgraphs. But suppose we don't look for complete subgraphs Ki, but rather try to find other subgraphs, such as cycle graphs (Cj), wheels (Wi), complete bipartite graphs (A',- ,), or trees? Problems such as these give rise to other families of Ramsey numbers, called graph Ramsey numbers. Definition 5 Suppose Gi,... ,Gn are graphs, each with at least one edge. An integer m has the (Gi,... ,Gn)-Ramsey property if every coloring of the edges of Km with the n colors 1, 2,... n yields a subgraph Gj of color j, for some j. The graph Ramsey number R(G\,... ,G„) is the smallest positive integer with the (Gi,..., G„)-Ramsey property. □ We note that, just as in the case of the classical Ramsey numbers discussed earlier, the "order" of particular colors does not matter. That is, if every coloring of Km has a red G\ or a green G2> then every coloring of Km has a green G\ or a red G2, and vice versa. Therefore, R(G\,G2) — R(G2,Gi), and the problem can be phrased as one of finding a monochromatic G\ or G2 (rather than a G\ or G2 of a specified color). taninplo 5 Some graph Hammy .......I.< 1 m. • ,i<,y to determine because Hli'V mii' the clRHnicul KaillNey number* in dlNglllHe Suppose we want to find /i'(ll',,f '.,), where 14-y is the wheel with 3 spokes Mini 1 , in the cycle of length :!. Since i.s the graph A'4 and g3 is a3, we have R(W3,C3) = R(K4, A3) = A>(4,3) = 9. imilarly, to find R(Kiti, W3), we must be able to guarantee either a red (i.e., a red edge) or a green W3. Therefore, R(K1A,W3) = R(K2,K4) = 4. The graph Ramsey numbers always exist, and are bounded above by re-I ii' 'I classical Ramsey numbers. To see this, suppose we wish to prove the iince of R(G\,... ,G„) where each graph Gj has ij vertices. If we let in R(ii,..., in; 2), then Theorem 4 guarantees that every coloring of Km with 1 Im n colors 1,2,..., n yields a subgraph AV of color j, for some j. But Gj is a subgraph of Ki., and hence we obtain a subgraph Gj of Km that has color j. Therefore R(G\.....G„) is bounded above by R(h,...,in;2). We state this as 1 he following theorem. Theorem 7 For j = 1,..., n, suppose that Gj is a graph with ij vertices (where ij > 2). Then the graph Ramsey number R(G\,..., Gn) exists, and A(G,,...,G„) < R{iu...,in;2). ■ This area of Ramsey theory has been a focus of much activity by many mathematicians, including Erdos and Graham*, during the last twenty years. See, for example Gardner [5] and Graham, Rothschild, and Spencer [6]. The case where a monochromatic A,- subgraph is "almost" obtained has also been studied. That is, rather than looking for the monochromatic A',- subgraphs (which is done when we try to find the classical Ramsey numbers R(i, j)), we look for monochromatic subgraphs A; — e, where A,- — e is the graph A,-with any one edge removed. The following example gives one of these numbers. * Ronald L. Graham (1935- ) was born in Taft, California, and received his bachelor's degree from the University of Alaska while in the Air Force. He received his Ph.D. from Berkeley (at which time he was also a member of a trampoline group) and then went to work at Bell Laboratories. At Bell Labs he has headed the Mathematical Studies Center and is currently Adjunct Director of the Research Information Sciences Division. His research work has been in the area of combinatorial mathematics, with many contributions in the field of Ramsey Theory. For his work in this area, in 1972 he was named a corecipient of the Polya Prize, given by the Society for Industrial and Applied Mathematics. He has also earned acclaim for his skill as a juggler, and has been past president of the International Jugglers Association. 154 Application ot Dlnovto Mathamatlct Example 6 Prove Mini, lt( r,l\;\ r) .I Solution: First note that A'3 — e is the graph <>u 3 vertices consisting of '.' edges. No matter how the 3 edges of A'3 are colored red or green, there are at least 2 of the same color, thereby giving the monochromatic subgraph A3 I Therefore R(I<3 — e, A'3 — e) < 3. It is easy to see that R(Ii3 — e, A3 — e) > 2, since we can take A'2 and color one edge red and the other green. Therefore R(I<3 - e, A3 - e) = 3. □ It is also known that fl(A'4-e,A4-e) = 10 R(Ks - e, K6 - e) = 22 42 6 by finding a coloring of the edges of A6 that has no red A'3 or green A'4. 3. Prove that if 0 < n < 5, then n does not have the (3,3)-Ramsey property. 4. Prove that R(2, k) — k for all integers k > 2. 5. Prove that R(i,j) = R(j, i) for all integers i >2,j> 2. 6. Suppose that m has the (i,j)-Ramsey property and n > m. Prove that n has the (i,j)-Ramsey property. 7. Suppose that m does not have the (f,j)-Ramsey property and n < m. Prove that n does not have the (i,,7')-Ramsey property. 8. Prove that R(i\,j) > R(t2,j) 'f h > «2- 9. In the proof of Lemma 1, prove that if |5| > R{i,j — 1), then m has the (j, j)-Ramsey property. *10. Suppose t > 3, j > 3, and R(i,j — 1) and R(i — are even integers. Prove that R(i, j) < R(i,j - 1) + R(i - - 1. (Hint: Follow the proof of Lemma 1, choosing the vertex v so that it has even degree.) 11. Prove that the graph in Figure 2(b) does not contain A'4 as a subgraph. ★12. Draw A13 and color its edges red and green according to the rule in Example 3. Then prove that the graph has no red A3 or green A5. 13. Use inequality (1) of Lemma 1 to prove that R(4,4) < 18. (Note: Roberts [9, p.330] contains a coloring of K\t that contains no monochromatic A4. This proves that #(4,4) = 18.) Ihli Awhaitions ol Dir., into pl,„ li llwiwtn NiimtHim 157 14. Prove that if 6* 11as nine vertices, then eilliei (, I•.• . n /\ , .111.>■,' ■'I>'1 ••' • • has a A'3 subgraph. 15. Prove Theorem 3. ★16. Suppose ii = ■ ■ • = i„ = 2. Prove that R(i\,. ..,»'„; 2) = 2, for all n > 2, ★17. Prove that R(7,3,3,3,3; 3) = 7. (/Vote: This example can be generalize to R(m, r, r,... ,r;r) = m if m > r). 18. Prove that 5(2) = 5 by showing that x + y = z has a monochronial li solution no matter how 1,2,3,4,5 are colored with two colors. ★19. Prove that 5(3) > 13 by showing that there is a coloring of 1,..., 13 with three colors such that the equation x+y = z has no monochromatic solution. ★20. Prove that for every five points in the plane (where no three are collinear), four of the five points can be connected to form a convex 4-gon. 21. Consider the following game for two players, A and B. The game begins by drawing six dots in a circle. Player A connects two of the dots with a red line. Player B then connects two of the dots with a green line. The player who completes a triangle of one color wins. a) Prove that this game cannot end in a draw. b) Prove that this game can end in a draw if only five dots are used. c) Suppose the game is played with six dots, but the player who completes a triangle of one color loses. Prove that the game cannot end in a draw. 22. Suppose the game in Exercise 20 is modified for three players, where the third player uses the color blue. a) Prove that the game can end in a draw if 16 points are used. b) Prove that there must be a winner if 17 points are used. 23. Suppose the game of Exercise 20 is played by two players with 54 dots, and the winner is the first player to complete a K5 of one color. If the game is played and happens to end in a tie, what conclusion about a Ramsey number can be drawn? 24. Verify that R(K1A,Klt3) = 4. ,1,1,1 ,11 , .1......luring* "I A% ,la,'r •■^rrr:sr.L-".....................*.......— .»:..................»™?« r- tttK!^* ,, ,|, ,rs such the the equation z + y - 2 has no mon Computer Projects 1. Write a computer program that proves that R(3,3) < 6, by examining all colorings of the edges of K$ and showing that a red K3 or a green K3 is always obtained.