off diagonal Ramsey number (4,k) lower bound probabilistic method asymptotic reasoning 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)$.
 A: 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$.
