FOM: Ramsey numbers

[Joe Shipman]

Urquhart:

>>In 1947, in one of the earliest and still most striking applications
of the probabilistic method, Erdos showed that
R(k,k) > 2^k.  The proof is amazingly simple, being nothing more than an
averaging argument (first moment method).<<

I don't think this is right -- the best asymptotic lower bounds look
like 2^(k/2) rather than 2^k.  The probability that a k-clique in a
randomly 2-colored graph is monochromatic is 2 * (1/2)^(k(k-1)/2) and if
you have significantly more than 2^(k/2) vertices then the number of
k-cliques will be too large for the counting argument to work.

For small k, the best known lower bounds seem much better than this.
For example, if k=10 the best the nonconstructive argument gets us is
that there is a 2-coloring of K_100 which has no monochromatic 10-clique
(proof: there are 17,310,309,456,440 10-cliques in K_100 and the
probability that a randomly colored one is monochromatic is
1/17,592,186,044,416).  On the other hand, Radziszowski's survey in the
Electronic Journal of Combinatorics attributes a lower bound of 798 for
R(10,10) to James Shearer (J. B. Shearer, "Lower Bounds for Small
Diagonal Ramsey
Numbers", Journal of Combinatorial Theory Series A, 42(1986), p.
302-304.)

Does anybody know for which k the simple nonconstructive lower bound for
R(k,k) becomes the best known bound?

-- Joe Shipman