FOM: Ramsey numbers
shipman at savera.com
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
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