MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What are the current best lower bounds for off-diagonal Ramsey numbers $R(k,l)$ with $l$ of order unity and asking for asymptotic behavior for large $k$, such as $R(k,4)$, $R(k,5)$, and so on? (please include any log factors, too!) Other than the more complicated arguments of Kim for $R(k,3)$, are all the other best lower bounds from the Lovasz local lemma?

share|cite|improve this question
Alon and Spencer say that the best lower bound on R(k, 4) is the one coming from the local lemma, but the situation might have improved since the book was written. – Qiaochu Yuan Nov 7 '10 at 23:14
up vote 6 down vote accepted

The best bounds I know of are due to Tom Bohman for $R(k,4)$ and Bohman and Peter Keevash for $R(k,5)$ and beyond. Both rely on using the differential equations method to analyze the following process: Start with the empty graph, and at each step add an edge uniformly at random among all edges which do not create a $K_t$. The bounds they achieve are $$R(k,t) \geq c_t \left( \frac{k}{\log k} \right)^{\frac{t+1}{2}} (\log k)^{\frac{1}{t-2}}$$

The final term in this product corresponds to the improvement over the bounds obtained using the Local Lemma. For $t=3$ it matches Kim's bound up to a constant factor.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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