FOM: Ramsey numbers

Joe Shipman shipman at
Mon Dec 4 16:24:12 EST 2000


>>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.

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

-- Joe Shipman

More information about the FOM mailing list