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

### Graphs - Proving the Infinite Ramsey Theory

```
Date: 11/10/97 at 10:00:30
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/
```
Associated Topics:
College Discrete Math
College Number Theory
High School Discrete Mathematics
High School Number Theory

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