off diagonal Ramsey number (4,k) lower bound probabilistic method asymptotic reasoning

Question

I want to show that $R(4,k)\ge\Omega((k/\ln k)^2)$, where $R(4,k)$ is the Ramsey number.

This question is quite close to what I'm after, the asymptotic part is only missing (and they talk about $3$ instead of $4$).

Similar to that question we define $Y$ and $Z$ as the number of $4-$cliques and the number of empty (no edges) sets of size (number of vertices) $k$ in a random Erdos-Renyi graph (a graph over $n$ vertices with edge probability $p$).<-- All of that is written in the answer to the quoted question.

So here is what I did to show that $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$.

Note: $p^6$ comes from an analogous argument as in the quoted question, $6$ is the number of edges in the complete graph on $4$ vertices. And I also suppose writing $\ge\Omega (...)$ is redundant, equality is OK.

First I restrict $n$ to be of the form $\frac{k^2}{(\ln k)^2}$ and I set $p:=1/n$. We get $${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ For the second term we have $${n\choose k}(1-p)^{k\choose 2}\le \frac{n^k}{k!}(1-\frac{\frac{1}{2}(\ln k)^2}{\frac{1}{2}k^2})^{k(k-1)/2}\\ \sim \frac{n^k}{k!} (\frac{1}{\sqrt k})^{\ln k}$$

This divided by $n$ is $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$ which we want to go to zero. This would imply it is $o(n)$.

This value is equal to $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ where the exponent goes to $-\infty$, which conlcludes the proof.

But I'm afraid I only showed $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ which is not the same as showing it is $\Omega(n)$.

Although I (think I) did that $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ which is a subclass of $\Omega(n)$.

Answer 1

If the asymptotic claims you've made really were true, then your proof would be fine. In particular:

• Yes, $n - o(n)$ is $\Omega(n)$. Even showing that $\binom nk (1-p)^{\binom k2} < 0.99n$ for large enough $n$ would be fine, and showing that it's $o(n)$ is stronger than that.
• Yes, assuming $n = (\frac{k}{\log k})^2$ without a constant is fine - if it works. We set $n = c (\frac{k}{\log k})^2$ for flexibility later on, so that we can choose a $c$ that will make our argument work. If $c=1$ happens to be fine, that's okay.

However, your asymptotic claims are false. In particular, $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ as $k \to \infty$. That's because

• $\log (n^{k-1}) = 2(k-1) \log k - 2(k-1) \log\log k \sim 2k \log k$ as $k \to \infty$;
• $\log(k!) \sim k \log k$ as $k \to \infty$ (this follows from Stirling's formula but here, it's enough that $\log(k!) < \log (k^k) = k \log k$);
• $\log\left(\sqrt{k}^{\log k}\right) \sim \frac12(\log k)^2 \ll k \log k$ as $k \to \infty$.

So you have $2 k \log k$ to start with in the exponent, and cancel out roughly $k \log k$ of it.

Your primary mistake is setting $p = \frac1n$. This is way too small. You need to set $p$ to be just small enough that you don't have to worry about the $\binom n4 p^6$ term; in particular, $p = \frac1{\sqrt n}$ is good enough. The larger $p$ is, the easier it will be to deal with the last term, so we don't want to make $p$ any smaller.

However, even then, setting $n = (\frac{k}{\log k})^2$ will not work - the constant matters here! I can tell you that $n = \frac14 (\frac{k}{\log k})^2$ and $p = \frac1{\sqrt n}$ will work; you should do the asymptotic analysis of that case yourself. You can get better results by playing around with the constants on $n$ and $p$.