most recent 30 from http://mathoverflow.net 2013-06-20T06:31:07Z http://mathoverflow.net/feeds/question/45232 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45232/best-lower-bound-for-off-diagonal-ramsey-numbers matt hastings 2010-11-07T23:08:52Z 2010-11-08T14:55:41Z

<p>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?</p>

http://mathoverflow.net/questions/45232/best-lower-bound-for-off-diagonal-ramsey-numbers/45311#45311 Kevin P. Costello 2010-11-08T14:55:41Z 2010-11-08T14:55:41Z

<p>The best bounds I know of are due to <a href="http://arxiv.org/abs/0806.4375" rel="nofollow">Tom Bohman</a> for $R(k,4)$ and <a href="http://arxiv.org/abs/0908.0429" rel="nofollow">Bohman and Peter Keevash</a> 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}}$$ </p> <p>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. </p>