From: kramsay@aol.com (KRamsay)
Subject: Re: Question: Graph Theory/Ramsey's Theorem
Date: 09 May 1999 01:42:17 GMT
Newsgroups: sci.math

In article <3733B6E9.E0FAF7AA@ucalgary.ca>, Arthur Fischer
<afischer@ucalgary.ca> writes:
|Essentially, the question ask for a proof that for any (undirected)
|graph of n nodes that their exists either a clique or an anti-clique
|(independent set) that contains at least (log_2 n) / 2 nodes.
|
|I have done a little bit of research to try to find a solution to this
|(probably simple) problem.&nbsp; I know that this question relates to
|Ramsey's
|Theorem, and hence to Ramsey Numbers.&nbsp; (Though I must admit to only
|rudimentary understanding of thse concepts at this point.)

Well, this *is* a result of Ramsey theory. Let R(m,n) be the smallest
N such that every graph with N verticies has either a clique of m
verticies or an anti-clique of n verticies. These are called Ramsey
numbers. Famously R(3,3)=6. The claim is equivalent to
R(k,k)<=2^{2(k-1)}+1. Evidently they think you might be able to figure
out a little Ramsey theory for yourself.

There's a story about Erdos. He said that if a demon were to come
threatening the human race if we didn't find the value of R(5,5), we
should get to work finding it, whereas if the demon demanded R(6,6),
we'd better try to find some way of getting rid of the demon, because
if we were so smart we could figure out R(6,6) just like that, we'd be
smart enough that a demon wouldn't be a problem.

Every so often, somebody moves one of the upper and lower bounds a
little, though.

The first little bit of _Ramsey Theory_ by Graham, Rothschild, and
Spencer gives an argument which is good enough for your exercise.
Sketch: show by induction that there is a sequence of verticies
v1,...,v_{2k-1} such that for each v_i, either v_i has an edge with
v_j for all j>i, or v_i does not have an edge with v_j for any j>i.
(Hint: take any vertex as v1.) Then take whichever subset of the
sequence is more numerous.

One defines a more general Ramsey number R(n1,...,nk) by coloring a
complete graph with k colors, and asking how many verticies are
required to force the existence of a clique having n_i verticies
connected by color i, for some 1<=i<=k. The R(m,n) are a special case
where we can color an edge red if it's in the original graph and blue
if it isn't.

Then there's an even more general Ramsey number R(s; n1,...,nk), where
instead of an ordinary graph (where the edges correspond to subsets
of order 2 of the verticies) we take a multigraph-- where the
multiedges correspond to subsets of order s.

The finite Ramsey theorem is that these numbers exist. Ramsey's
original theorem was the infinite theorem, that if there are
infinitely many vertices, then there is an infinite monochromatic
clique. He was proving these results for an application to logic, a
decision procedure for statements in predicate calculus having some
restricted form (only universal quantifiers or something like that).
The algorithm isn't very effective; it relies upon the fact that
searching all the possibilities which aren't large enough to force a
monochromatic clique is finite.

Transfinite versions of Ramsey's theorem appear in set theory; some of
them are independent of ZF, naturally.

Frank Plimpton Ramsey was sort of an interesting guy, although he
didn't live very long (1903-1930). Economists remember him for some
papers he wrote. He had some platonic reflections in the philosophy
of mathematics. He had something to say about probability theory, I
think. He once said that he didn't regard human beings as small and
insignificant; he saw us as being in the foreground, prominently, much
more important than all those large structures in the background.

My father and I thought it would be amusing to prove some result in
Ramsey theory as a kind of joke. :-) Kind of difficult joke, though.

Keith Ramsay
Boulder, CO      But not related to JonBenet Ramsey either!