Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.