Graphs - Proving the Infinite Ramsey Theory

Date: 11/10/97 at 10:00:30
From: T. Madarasz
Subject: Graphs (Ramsey)

How can you prove the infinite Ramsey theory? (We have a graph with 
infinite "points"; if we colour the lines with two colours (e.g. red 
and blue) we'll have an infinite chain of either red or blue lines 
- infinite numbers of points, all of them joined to each other with 
the same colour.

Also I need the smallest x for which X->(4,4) is true, i.e., if  a 
graph with x points is coloured with two colours there will be either 
a red or a blue full quadrilateral.

Date: 11/10/97 at 13:55:07
From: Doctor Wilkinson
Subject: Re: Graphs (Ramsey)

Here's the general idea of proving the infinite version. We're going 
to try to build up the infinite chain one point at a time.

Let's say a point has finite red degree if it has only finitely many 
red lines coming out of it. Suppose first that there are infinitely 
many points of finite red degree. Then just look at the graph formed 
by those points. 

Let x1 be any such point. It has infinitely many blue lines coming 
from it, so we consider just the points at the ends of those lines, 
and let x2 be one of them. x2 also has infinitely many blue lines 
coming from it, so we consider just the points at the ends of those 
lines, and let x3 be one of those. Continuing this process, we build 
up an infinite blue chain.

So we can suppose that the are only finitely many points of finite red
degree. Toss them away. Now all the points have infinite red degree.  
Let x1 by any one of them. The points joined to it by red lines are 
infinite in number, and again we can ask whether the number of such 
points of finite red degree is finite or infinite. If it's infinite, 
we continue. If it's finite we are in case 1. In any case we build up 
either an infinite red chain or an infinite blue chain.

Technically you need a set-theoretic axiom called "Zorn's Lemma," 
equivalent to the so-called "Axiom of Choice" to pass from a sequence 
of ever-larger finite chains to an infinite chain.

The answer to your second question is 18.

-Doctor Wilkinson,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/