Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

```

```
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

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/
```
Associated Topics:
College Definitions
College Number Theory
High School Definitions
High School Number Theory
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search