  In a seminal paper, Erdos and Renyi identified the threshold for connectivity
of the random graph G(n,p). In particular, they showed that if p >> log(n)/n
then G(n,p) is almost always connected, and if p << log(n)/n then G(n,p) is
almost always disconnected, as n goes to infinity.
  The clique complex X(H) of a graph H is the simplicial complex with all
complete subgraphs of H as its faces. In contrast to the zeroth homology group
of X(H), which measures the number of connected components of H, the higher
dimensional homology groups of X(H) do not correspond to monotone graph
properties. There are nevertheless higher dimensional analogues of the
Erdos-Renyi Theorem.
  We study here the higher homology groups of X(G(n,p)). For k > 0 we show the
following. If p = n^alpha, with alpha < -1/k or alpha > - 1/(2k+1), then the
kth homology group of X(G(n,p)) is almost always vanishing, and if -1/k < alpha
< -1/(k+1), then it is almost always nonvanishing.
  We also give estimates for the expected rank of homology, and exhibit
explicit nontrivial classes in the nonvanishing regime. These estimates suggest
that almost all d-dimensional clique complexes have only one nonvanishing
dimension of homology, and we cannot rule out the possibility that they are
homotopy equivalent to wedges of spheres.
