I am trying to understand the proof for this theorem about the threshold for cliques of 4 or more vertices:
I do not understand what $p = o(n^{-2/3})$ means; is this a bound on the number of edges? If so, then does this mean that if we have 1000 vertices, then $p = o(0.1)$? I also do not understand how we got to $p^6$ in the last equation. I realize that we can find the expected number of cliques with the number of vertices and edges, but I am having difficulties understanding it here. I may discover this after further reading, but what is the meaning of $n^{-2/3}$, and how did we come to this number/threshold?
Given two functions $f,g$ in $n$, we write $f(n)=o(g(n))$ if $\frac{f(n)}{g(n)}$ tends to zero as $n$ tends to infinity.
About the last equation, you have $E(X)=\sum E(X_i)$ and $$E(X_i)=1*P(X_i=1)+0*P(X_i=0)=P(X_i=1)$$ but $P(X_i=1)=p^6$ for each $i$ (Why? This is the probability that $C_i$, which is a set of four vertices, forms a cliques of 4).
$n^{-2/3}$ comes up just by doing the reverse reasoning: we have $E(X)={n\choose 4}p^6$ and we want $E(x)$ to go to zero as $n$ goes to infinity. But $${n\choose 4}p^6\leq\frac{n^4}{4!}p^6\leq n^4p^6=\left(n^{2/3}p\right)^6$$ So it's good enough if $n^{2/3}p$ goes to zero as $n$ goes to infinity; note that this is equivalent to write $p=o(n^{-2/3})$.