Combinatorics: Ramsey Theory
Date: 01/12/98 at 22:50:00 From: John W. Busardo Subject: Ramsey Theory Dr. Math, In two months I have an oral presentation due concerning combinatorics. Mainly it is a presentation on Ramsey theory. The project must include a detailed explanation of the theory along with a concrete example. We must be able to explain this example. Is there any way you could help me find this information? I have searched everywhere possible on the Web and I can not seem to find a description, or a concrete example with explanation. Thank you for your help.
Date: 01/13/98 at 15:47:39 From: Doctor Anthony Subject: Re: Ramsey Theory Ramsey's Theorem ----------------- Suppose we have six points joined in pairs by arcs coloured either red or blue. We are asked to show that there are three points such that the arcs of the triangle they form are of the same colour. We can demonstrate this in the following way. Take one point P(0) and consider the five arcs from P(0) to the remaining five points. Three of these arcs must be of the same colour (say red); let these be numbered P(0)P(1), P(0)P(2), P(0)P(3). If any one of the arcs P(1)P(2), P(1)P(3) or P(2)P(3) is red, this arc together with the two arcs joining its ends to P(0) form a red triangle. Otherwise all three of P(1)P(2), P(1)P(3) and P(2)P(3) are blue and P(1)P(2)P(3) is a blue triangle. This solves the problem and it is easy to see that six is the right number of points to guarantee a triangle of one colour. The following list gives an example of a set of five points, with red and blue arcs joining the pairs so that there is no triangle of one colour. P(1)P(2): red P(2)P(4): red P(1)P(3): red P(2)P(5): blue P(1)P(4): blue P(3)P(4): blue P(1)P(5): blue P(3)P(5): red P(2)P(3): blue P(4)P(5): red The problem may be generalized and the solution given above can also be generalized. The generalization is known as Ramsey's theorem. Let S be a set containing N elements (e.g. the six points in the original example above), and suppose that the family T of all subsets of S containing exactly r elements (e.g. 2 points forming an arc, so r = 2) is divided into two mutually exclusive families, alpha and beta (e.g. red arcs and blue arcs). Let p > or equal r, q > or equal r, r > or equal 1. Then if N is greater than or equal to n(p,q,r), a number depending solely on the integers p, q, r and not on the set S, it will be true that there is either a subset A of p elements, all of whose r subsets are the family alpha, or there is a subset B of q elements, all of whose r subsets are in the family beta. So in our illustrative example p = q = 3 and A is the set of triangles with 3 red arcs forming the alpha family, and B is the set of triangles with 3 blue arcs forming the family beta. The problem solved above shows that n(3,3,2) is at most 6 and that n(3,3,2) is greater than 5. So we can say n(3,3,2) = 6 exactly. The proof of the general theorem is by induction, and is pretty opaque not to put too fine a point on it. Assuming it is true, the following are further theorems that are based on Ramsey's theorem: For a given integer n, there is an integer N = N(n) such that any N points in a plane, no three being collinear, will contain n points forming a convex n-gon. (A body is convex if any line segment joining two points of it lies entirely in the body.) Example: Of five points in a plane, no three on a line, four are the vertices of a convex quadrilateral. Also; if all the quadrilaterals are formed from n points, and no three in a line are convex, then the n points are the vertices of a convex n-gon. The following are a series of problems based upon Ramsey's theorem. (1) Given six points joined in pairs by either a blue or red arc. Calling a triangle 'chromatic' if its three arcs are of the same colour, show that there must be at least two chromatic triangles. (2) Using the result of question (1), show that given seven points joined in pairs by either a blue or red arc, there must be at least four chromatic triangles. (3) Prove that n(k,m,2) = n(m.k,2) when m> or = 2, k> or = 2. (4) Prove that for k>=2, m>=2 n(k,m,2) = ( k+m-2) = ( k+m-2) ( k-1 ) ( m-1 ) where the expressions are binomial coefficients C(k+m-2,k-1) etc. (5) Prove that n(3,4,2) <= 9, where alpha is red, beta blue. Show that the conclusion holds if there are are four red arcs or six blue arcs at a vertex. Show that it is impossible to have three red arcs and five blue arcs at every vertex because the numbers 3, 5, and 9 are odd. (6) Prove n(3,4,2) > 8 and so n(3,4,2) = 9, by taking vertices as the residues modulo 8 (0,1,2,...7) and making the colour of the arc joining i and j depend only on the difference i-j (mod 8). Note that we must assign the same colour to d = i-j and -d = j-i. (7) Show that n(4,4,2)>17 by taking vertices as the residues 0,1,..16 (mod 17) and denoting as blue the arc joining i and j if i-j = +-1, +-2, ... +-8 (mod 17) and red otherwise. Hence conclude that n(4,4,2) = 18. -Doctor Anthony, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.