  For a graph G, the neighborhood complex N[G] is the simplicial complex having
all subsets of vertices with a common neighbor as its faces. It is a well known
result of Lovasz that if N[G] is k-connected, then the chromatic number of G is
at least k + 3.
  We prove that the connectivity of the neighborhood complex of a random graph
is tightly concentrated, almost always between 1/2 and 2/3 of the expected
clique number. We also show that the number of dimensions of nontrivial
homology is almost always small, O(log d), compared to the expected dimension d
of the complex itself.
