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/