Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$

Question

Let $G = (V, E)$ be a uniform random graph on $2n$ labeled vertices and let $S \subseteq {V}$ be the set of vertices with degree $\ge n$. Then what happens to $\mathbf{P}(|S|=n)$ as $n \to \infty$?

From the Harris-Kleitman inequality one can obtain $\mathbf{P}(|S|=n) \le c_n$, where $c_n \to \frac{1}{2}$. I found a way to prove that $\mathbf{P}(|S|=n) \le c_n$, where $c_n \to \sqrt{2}-1$. Is it possible to obtain a better bound? Can we prove that this probability converges to $0$ or is bounded from below?

Answer 1

It certainly tends to $0$. The way to see it almost without any computation is to mark any $n$ disjoint edges. Then, when deciding the fate of the remaining edges, each vertex has $p=2^{2-2n}{2n-2\choose n-1}\asymp n^{-1/2}$ chance to get the degree of exactly $n-1$ and these events for two distinct vertices are almost uncorrrelated, so the variance of the number of such "critical" vertices is much less than the square of the expectation, and, thereby, with high probability, we get the number of critical vertices comparable to $\sqrt n$. Deciding the fate of the marked edges for those critical vertices creates essentially the standard random walk with about $\sqrt n$ steps $0$, $1$, or $2$, which cannot be concentrated on any value by much more than $n^{-1/4}$, so we have proved a (rather weak) power decay. The actual bound should be $cn^{-1/2}$ and we should have the CLT, but I do not see a two-line proof of that though I have no doubt that it is well-known and written nicely somewhere...