Best lower bound for off-diagonal Ramsey numbers

Question

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?

Answer 1

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.