We create a random graph $G(n,1/2)$.
Next, we choose randomly $k$ vertices, and form a clique out of these $k$ vertices.
My question is: how do you prove (with high probability) that when
$$k > C {\sqrt{n{\log(n)}}}$$
for some sufficiently large constant $C$, that the vertices of the clique are the highest degree vertices in the graph?
This answer expands upon Rodrigo Ribeiro's solution. Specifically, that by using Chernoff bound \begin{equation} P(Bin(\nu, 1/2) \geq \nu/2 +\lambda) \leq \exp \left( - \frac{ \lambda^2}{\nu+2\lambda/3} \right), \end{equation} by choosing $\lambda=1.1 \sqrt{n \ln n}$, one can show that with probability tending to 1, each vertex in $G(n, p=1/2)$ has degree in the interval $$[n/2-1.1\sqrt{n \ln n}, n/2+1.1\sqrt{n \ln n}].$$
Now we wish to find a $C>0$, such that with high probability, if we randomly choose a set of vertices of size $\ell:=\sqrt{C n \ln n}$ and add any missing edges, then at least one has degree greater than $n/2 + 1.1 \sqrt{n \ln n}$. For ease, let's say that an $\ell$-set is a set of $\ell$ vertices. Let $X$ be the number of $\ell$-sets such that there is a vertex (in this $\ell$-set) that is adjacent to at least $2\ell/3$ of the other $\ell-1$ vertices. If we choose a $\ell$-set that doesn't correspond to $X$, then each vertex has their degree increased by at least $\ell/3$. Hence, we want to show that (1st) $\ell/3 \gg 2.2 \sqrt{n \ln n}$ (so that each vertex in this $\ell$-set has degree larger than $n/2+1.1\sqrt{n \ln n}$) and that (2nd) the probability that we choose an $\ell$-set corresponding to $X$ tends to zero.
For the first, since $\ell=\sqrt{C n \ln n}$, it is enough to choose $C=9$.
For the second, by Markov's Inequality, \begin{equation*} P(X> \ln n \, E[X]) \leq 1/\ln n. \end{equation*} Since we initially choose the $\ell$-set uniformly at random, the probability that we choose an $\ell$-set corresponding to $X$ is \begin{equation*} P(\text{choose an }\ell\text{-set from }X)=\sum_{b=0}^{{n \choose \ell}} P(X=b) \frac{b}{{n \choose \ell}} \leq \frac{ \ln n \, E[X]}{{n \choose \ell}}+P(X> \ln n \, E[X]). \end{equation*} The second term is bounded by $1/\ln n$. Now we need to bound $E[X]$. So \begin{align*} E[X] &\leq {n \choose \ell} P(\{1, \ldots, \ell\}\text{ belongs to }X) \\ &\leq {n \choose \ell} \ell \, P(\{1\} \text{ is adjacent to at least }2\ell/3\text{ of }\{2, \ldots, \ell\}) \\ &\leq {n \choose \ell} \ell \, P(\text{In }G(\ell, 1/2),\, \text{deg}(1) \geq \ell/2+\ell/6). \end{align*}
Using Chernoff's bound again, we get that \begin{align*} P(\text{In }G(\ell, 1/2),\, \text{deg}(1) \geq \ell/2+\ell/6)\leq \exp \left( -\frac{\ell^2/36}{10\ell/9}\right) = \exp \left( - \ell/40 \right). \end{align*}
Therefore \begin{equation*} P(\text{choose an }\ell\text{-set from }X) \leq \ln n \, \ell \, e^{-\ell/40} +\frac{1}{\ln n}. \end{equation*} Both of these terms tend to zero.
In this argument, we got that we could choose $C=9$. With using this Chernoff bound, it seems (to me) that the best one could get is any $C>4$.
I'm assuming that you look to the degrees after the formation of your clique, ok?
Observe that if $v \in V(G) $ then $ deg(v) \sim bin(n-1, 1/2) $, right? What you know about random variable with binomial distribution? They are exponentially close to its mean. Using Chernoff Bound
$$ P(deg(v) > n/2 + \lambda) \le exp\{-\frac{\lambda^2}{2(n/2+\lambda/3)}\}$$
If you let $ \lambda = \sqrt{Cnlog(n)}$ what you have, for $n$ large, is
$$ P(deg(v) > n/2 + \sqrt{Cnlog(n)}) \le n^{-C} $$
Actually you have a very simular inequality for $P(deg(v) < n/2 - \lambda)$, so you have
$$ P(|deg(v) - n/2| > \sqrt{Cnlog(n)}) \le 2n^{-C}$$ and finally
$$P(\exists v \text{ such that } |deg(v) - n/2| > \sqrt{Cnlog(n)} ) \le 2n^{-C+1} $$
We proved that the degree of all vertices are close to $n/2$, if $C>1$, and they can't have a deviation of $\sqrt{Cnlog(n)}$.
But observe that all the vertices in the clique have their degrees increased by $k-1$, so if you let $k > \sqrt{Cnlog(n)}$ you have the result with high probability.
