Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Previously I have shown that for any positive integers $k,l$, and any real number $p\in (0,1)$, ramsey number $R(l,k) \geq n- {n\choose k} p^{{k \choose 2}} - {n\choose l} (1-p)^{{l \choose 2}}$.

Now I want to show, by using the above that $$R(3,k) \geq c (\frac{k}{log k})^a$$ for $a$ and $c$ positive constant.

I tried using stirling approximation i.e: from the first inequality above: $$ R(3,k) \geq n - (\frac{ne}{k})^k p^{k/2} - (\frac{ne}{3})^3 (1-p)^3$$

Now I thought of trying to do some analysis on the function: $$f(x)=1-Ax^{k-1}-Bx^2$$

But I believe this makes it more obsecure, and I don't see how to get out of this.

Any hints, answers, wishful thoughts? :-)

Thanks in advance.

share|cite|improve this question
General heuristic when optimizing sums of the form $A-B$ with $A$ and $B$ depending on several parameters, some of which push $A$ to be bigger, and some push $B$ small is to make $A\approx B$ (i.e., same up to a factor of $2$ say). Practically always it gives answer which is only a constant factor off the optimal (which can be found by doing Lagrange multipliers). – Boris Bukh Apr 9 '12 at 9:52
What is $n$ in your formulae? – Christian Blatter Apr 9 '12 at 10:23
@Blatter, in this question $n \geq k+l$. – MathematicalPhysicist Apr 9 '12 at 10:58

Your Answer


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

Browse other questions tagged or ask your own question.