The neighborhood complex of a random graph

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 Lovász 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(logd), compared to the expected dimension d of the complex itself.