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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Nov 7 '10 at 23:14

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.


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.