# Probability of k-clique in a random graph

I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$. $X_k$ is the random variable which count the number of k-cliques in a random graph. I already know $E[X_k] = \binom{n}{k}(\frac{1}{2})^{\binom{k}{2}}$. I don't know exactly how to find the exact value of k. I know $P[X_k \geq 1] \leq E[X_k]$ for Markov inequality but I'm not sure that this is helpful. Thanks in advance

The value is $2\log_2 n - 2\log_2\log_2 n + O(1)$.
Let $k_0$ be the maximal value such that the expected number of cliques of size $k_0$ is at least 1. A boring calculation shows that $k_0 = 2\log_2 n - 2\log_2\log_2 n + O(1)$. It is a classical result that with high probability, $G(n,1/2)$ contains a $(k_0-1)$-clique. This implies that $k > k_0-1$. On the other hand, it is known that the expected number of cliques of size $k_0+1+C$ is $O((\log n/n)^C)$ for any constant $C$ (this is because the expected number of cliques drops by $\Theta(\log n/n)$ near $k_0$). This shows that $k \leq k_0+3$. We conclude that $k_0 \leq k \leq k_0+3$.
• Could you please clarify the calculation for $k_0$? And what is that classical result you mentioned? – Pratozoo Jan 14 '18 at 18:07