FOM: Re: Ramsey numbers

[Alasdair Urquhart]

Joe Shipman is quite right, I made a careless mistake 
with Erdos's lower bound.  Erdos's 1947 paper gives 
the bounds

	2^(k/2) < R(k,k) < 4^(k-1).

By using the Lovasz local lemma, the lower bound can be
improved to 

	k*2^(k/2)*[ sqrt(2)/e + o(1)] < R(k,k).

On the terminological question, the term "Pigeonhole principle"
is more or less a straight translation of Dirichlet's
"Schubfachprinzip" into (Victorian) English.  The term
"pigeonhole" refers to one of those old-fashioned writing
desks with thin vertical wooden partitions in which to
file letters.  These obviously looked a little like
the pigeon roosts in dovecotes, hence the name.

Alan Woods is visiting here in Toronto at the moment, and mentioned
to me that (if I remember correctly) Pavel Pudlak has some
results deducing results on Ramsey's theorem from the pigeonhole
principle in weak systems of bounded arithmetic.  I don't know
the details of this -- perhaps some FOM subscriber knows more.


Alasdair Urquhart