Using the first moment method, in 1947 Erd\H{o}s gave a lower bound on the diagonal Ramsey numbers $R(k,k)$: $$ R(k,k) \geq (1+o(1))\frac{k}{e\sqrt{2}} 2^{k/2}. $$ In 1975 Spenser used the Lov\’asz Local Lemma to improve this by a factor of $2$, to $(1+o(1))(k\sqrt{2}/e)2^{k/2}$.

In between these two lower bounds, there is the one you get via the alteration or deletion method: $$ R(k,k) \geq (1+o(1))\frac{k}{e} 2^{k/2}. $$

I’m trying to discover who first noticed this last bound, and when? Was it before or after Spencer’s improvement? I’ve seen the bound in numerous sets of notes online (and learned it as a graduate student), but with no attribution. Maybe it’s just ``folklore’’.

(I’m leading a summer reading group in Ramsey Theory, and I plan on Tuesday to tell them the history of upper and lower bounds on diagonal Ramsey numbers.)


On p.54 of "Recent Developments in Graphy Ramsey Theory" by Conlon, Fox, Sudakov which appeared in the monograph Surveys in Combinatorics 2015, Czumaj et. al. (eds), is the footnote below:

Though we do not know of an explicit reference, a simple application of the deletion method which improves Erdos' bound by a factor of $\sqrt{2}$ was surely known before Spencer's work.

Sounds like it may well be folklore.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.