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 . ve 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.