Let $K_n$ denote a complete graph with $n$ vertices. Given any positive integers $k$ and $l$, the Ramsey number $R(k, l)$ is defined as the smallest integer $n$ such that in any two-coloring of the edges of $K_n$ by red and blue, either there is a red $K_k$ or a blue $K_l$.

(i) Prove if there is a real $0 \leq p \leq 1$ such that

$$\binom{n}{4}p^6 + \binom{n}{k}(1-p)^{\binom{k}{2}} < 1 $$ then we have $R(4,k) > n$.

(ii) Use the previous part to show that there exists a constant $c > 0$ such that $$ R(4,k) \geq c \Big(\dfrac{k}{log(k)}\Big)^{3/2} $$

I have no problems proving the first part. You let $p$ to be the probability of choosing a red edge, compute the probability of at least one red complete graph of size $k$, and blue graph of $l$, finally conclude that with positive probability there exists a graph such that it contains no red and blue complete graphs of the mentioned sizes, and therefore $R(4,k) > n$.

However, how to proceed for the second part? I am studying the probabilistic method and lots of exercises with finding constants. What should the sketch of the proof look like?

UPDATE: I have reduced the question to finding a constant satisfying $log(n) < n^{-2/3}k/4$. Also, the screenshot is from a claimed solution manual: enter image description here How is the right $n$ value concluded here?

  • $\begingroup$ “constant satisfying $log(n) < n^{-2/3}k/4$” what is a constant here? $\endgroup$ – Alex Ravsky Dec 27 '18 at 3:34
  • $\begingroup$ @AlexRavsky I think that's also what I wonder. After the inequality in your comment, it says "but there exists a constant $c$ such that $n = c(k/log(k))^{3/2}$ satisfies this inequality". Doesn't $c$ here depend on $n,k$? If I just try to make it similar to the expression in the question, of course it's possible with $c$ depending on $n,k$ but does that make it a constant? I may be missing the jargon here too. $\endgroup$ – user2694307 Dec 27 '18 at 11:09
  • $\begingroup$ The constant $c$ should be independent of both $n$ and $k$. $\endgroup$ – Misha Lavrov Dec 29 '18 at 5:55

To use part (i) to show part (ii), your goal is to find some $n$ of the required form, and some probability $p$, such that the inequality in part (i) holds.

If we're hoping for the best result possible, the two terms ought to contribute about equally: both $\binom n4 p^6$ and $\binom nk (1-p)^{\binom k2}$ ought to be constants. This motivates choosing $p = n^{-2/3}$ so that $\binom n4 p^6 < \frac{n^4 p^6}{24} = \frac{1}{24}$.

Next, we want to put some upper bounds on $\binom nk (1-p)^{\binom k2}$ to make it easier to work with. For the binomial coefficient, a good general bound to use is $\binom nk \le \left(\frac{ne}{k}\right)^k$. (A much weaker bound like $\binom nk \le n^k$ also works, but there's no way to know that ahead of time.) Meanwhile, $1-p \le e^{-p}$, so $(1-p)^{\binom k2} \le e^{-pk(k-1)/2}$.

Putting these together lets us collect the power of $k$: $$ \binom nk (1-p)^{\binom k2} \le \left(\frac{ne}{k}\right)^k e^{-pk(k-1)/2} = \left(\frac{ne}{k e^{p(k-1)/2}}\right)^k. $$ To make sure that this result is less than $\frac{23}{24}$, we need to make the base of the exponent less than $1$. The key to this is to make the $e^{pk/2}$ in the denominator cancel out the $n$ in the numerator. This is why $n^k$ is as good a bound on $\binom nk$ as $\left(\frac{ne}{k}\right)^k$ is: the $k$ isn't really helping. If we use $\binom nk \le n^k$, we get $$ \binom nk (1-p)^{\binom k2} \le n^k e^{-pk(k-1)/2} = \left(\frac{n}{e^{p(k-1)/2}}\right)^k. $$ Either way, we want to get $p \cdot \frac{k-1}{2} > \log n$, or $k > \frac{2 \log n}{p} + 1$. We don't care about the constant, though, so let's just ask for $k \ge \frac{3\log n}{p}$.

Since we set $p = n^{-2/3}$, this means that $k \ge 3 n^{2/3} \log n$. This is the answer, in a way, but it expresses the reverse relationship; we want a bound on $n$ in terms of $k$.

Assuming $n \le k^2$, we satisfy $k \ge 3 n^{2/3} \log n$ if we satisfy $k \ge 3n^{2/3} \log (k^2) = 6 n^{2/3} \log k$. Solving for $n$, this gives $n \le \left(\frac{k}{6\log k}\right)^{3/2}$.

(This, in addition to having the form we want, is stricter than $n \le k^2$ for all $k>1$, justifying our earlier assumption.)


OK, I looked at Joel Spencer’s “Ten Lectures on the Probabilistic Method”. By the way, according to its contents, it has many applications in Ramsey Theory. In particular, the sketch of the proof for your problem is at p. 4.

But I remark that this lower bound for Ramsey number is very weak. At p. 63 Spencer writes:

What about $R(4,k)$? The basic probabilistic method gave a lower bound $k^{3/2+o(1)}$. The deletion method improved this to $k^{2+o(1)}$. From the Lovász Local Lemma one may obtain (try it!) $R(4,k)> k^{5/2+o(1)}$. The upper bound is $R(4,k)<k^{3+o(1)}$, so a substantial gap still remains.


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.