Expected number of $k$-cliques in $G(n, 1/2) \ge 1$ Let the expected number of $k$-cliques be denoted by
$$f(k) = \binom{n}{k} (\frac{1}{2})^{- \binom{k}{2}}$$
let $k_0$ denote the largest $k$ such that $f(k) \ge 1$.
I want to prove that $k_0 = (1+o(1)2log_{2}n$ and $n = \Theta(k_0 2^{k_0/2})$.
I can prove that $G(m, 0.5)$ has no clique of size $2log_{2}(n)$ almost surely using Markov, but does this help?
Any help very much appreciated!
 A: This is just a sketch, the (gory) details of the calculations are left.
Note that $f(k)/f(k+1)=\frac{n-k}{k+1} (\frac{1}{2})^{k}$ which is a decreasing function of $k$. So the ratio is at least 1 up to a certain value, then it is at most 1. So we have that $f$ increases from $f(0)=1, f(1)=n, \dots$ (a certain value), then it decreases.
Given the above, instead of taking $k_0$, we can consider $k_1=\min \{k: f(k)<1\}$ and show $k_1 \sim 2\log_2(n)$ as $n$ goes to infinity.
To show this, use the classic estimates on the binomial coefficients (see the first formula in "Bounds and asymptotic formulas" HERE ) and consider the $k$-th root of $f(k)$. The bounds given in the link imply $f(k)^{1/k}= \Theta(\frac{n}{k} (\frac{1}{2})^{k/2})$ 
Fix $\epsilon >0$ and show: if $k\leq (1-\epsilon)2 \log_2(n)$, then $f(k)>1$ (hence $k_1 \geq k$) and if $k\geq (1+\epsilon)2 \log_2(n)$, then $f(k)<1$ (hence $k_1 \leq k$).
The proof of the first case goes as follows: if $k\leq (1-\epsilon)2 \log_2(n)$, then $(1/2)^{k/2} \leq n^{1- \epsilon}$. Hence $f(k)^{1/k} \geq Cn(n^{-1+\epsilon})/\log(n)$, where $C$ is a constant. This is bigger than 1 for $n$ large enough.
A similar argument show that $f(k)<1$ for $k\geq (1+\epsilon)2 \log_2(n)$.
