Graphs - Proving the Infinite Ramsey TheoryDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/