FOM: Re: Ramsey numbers
Alasdair Urquhart
urquhart at cs.toronto.edu
Mon Dec 4 20:28:48 EST 2000
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
More information about the FOM
mailing list