zbMATH — the first resource for mathematics

The neighborhood complex of a random graph. (English) Zbl 1110.05090
Summary: For a graph $$G$$, the neighborhood complex $$\mathcal {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 L. Lovász [J. Comb. Theory, Ser. A 25, 319–324 (1978; Zbl 0418.05028)] that if $$||\mathcal {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.

MSC:
 05C80 Random graphs (graph-theoretic aspects) 05C15 Coloring of graphs and hypergraphs
Keywords:
coloring; morphism complexes
Full Text:
References:
 [1] Babson, E.; Kozlov, D., Topological obstructions to graph coloring, Electron. res. announc. amer. math. soc., 9, 61-68, (2003) · Zbl 1063.05041 [2] Babson, E.; Kozlov, D., Complexes of graph homomorphisms, Israel J. math., 152, 285-312, (2006) · Zbl 1205.52009 [3] E. Babson, D. Kozlov, Proof of the Lovász conjecture, arXiv: math.CO/0402395, Ann. of Math., in press [4] Bollobás, B., Random graphs, (2001), Cambridge Univ. Press · Zbl 0997.05049 [5] Björner, A., Topological methods, (), 1819-1872 · Zbl 0851.52016 [6] P. Csorba, Homotopy types of box complexes, arXiv: math.CO/0406118, Combinatorica, in press [7] Csorba, P.; Lange, C.; Schurr, I.; Wassmer, A., Box complexes, neighborhood complexes, and the chromatic number, J. combin. theory ser. A, 108, 159-168, (2004) · Zbl 1060.05029 [8] Dochtermann, A., Hom complexes and homotopy theory in the category of graphs, arXiv: · Zbl 1167.05017 [9] C. Hoffman, M. Kahle, Simple connectivity of random 2-dimensional simplicial complexes, in preparation [10] M. Kahle, Topology of random clique complexes, in preparation · Zbl 1215.05163 [11] Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. combin. theory ser. A, 25, 319-324, (1978) · Zbl 0418.05028 [12] N. Linial, R. Meshulam, Homological connectivity of random 2-complexes, Combinatorica, in press · Zbl 1121.55013 [13] C. Schultz, The relative strength of graph coloring obstructions, preprint, 2006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.