The neighborhood complex of a random graph

Matthew Kahle
Journal of Combinatorial Theory, Series A
Volume 114, Issue 2 , February 2007, Pages 380-387
http://dx.doi.org/10.1016/j.jcta.2006.05.004

LovaszがKneserグラフの染色数を定めるために用いたneighborhood complex (近傍複体) に関する話．
いわゆるErdos-Renyiモデルのランダム・グラフの近傍複体の連結度やホモロジー群を調べている．