×

Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes. (English) Zbl 1105.57021

The author proves that for a graph \(G\), the neighborhood complex \(\mathcal N(G)\) and (the barycentric subdivision of) the polyhedral complex \(\text{Hom}(K_2,G)\) of graph homomorphisms have the same simple homotopy type, that is, one can be obtained from the other by a finite sequence of collapses and anti-collapses. Here \(K_2\) denotes the complete graph on two nodes.

MSC:

57Q10 Simple homotopy type, Whitehead torsion, Reidemeister-Franz torsion, etc.
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alexander, J. W., The combinatorial theory of complexes, Ann. of Math., 31, 292-320 (1930) · JFM 56.0497.02
[2] Björner, A., Topological methods, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), Elsevier: Elsevier Amsterdam), 1819-1872 · Zbl 0851.52016
[3] Babson, E.; Kozlov, D. N., Topological obstructions to graph colorings, Electron. Res. Announc. Amer. Math. Soc., 9, 61-68 (2003) · Zbl 1063.05041
[4] Babson, E.; Kozlov, D. N., Complexes of graph homomorphisms, Israel J. Math., in press · Zbl 1205.52009
[5] Babson, E.; Kozlov, D. N., Proof of the Lovász Conjecture, Ann. of Math. (2), in press · Zbl 1132.05019
[6] Csorba, P., Homotopy type of the box complexes, Combinatorica, in press · Zbl 1236.05067
[7] Cohen, M., A Course in Simple-Homotopy Theory, Graduate Texts in Math., vol. 10 (1973), Springer: Springer New York · Zbl 0261.57009
[8] Čukić, S. Lj.; Kozlov, D. N., The homotopy type of the complexes of graph homomorphisms between cycles, Discrete Comput. Geom., in press · Zbl 1103.55003
[9] S. Lj. Čukić, personal communication, 2005; S. Lj. Čukić, personal communication, 2005
[10] Čukić, S. Lj.; Kozlov, D. N., Higher connectivity of graph coloring complexes, Internat. Math. Res. Not., 25, 1543-1562 (2005) · Zbl 1077.05038
[11] Feichtner, E.-M.; Kozlov, D. N., Incidence combinatorics of resolutions, Selecta Math. (N.S.), 10, 1, 37-60 (2004) · Zbl 1068.06004
[12] Forman, R., Morse theory for cell complexes, Adv. Math., 134, 1, 90-145 (1998) · Zbl 0896.57023
[13] Goresky, M.; MacPherson, R., Stratified Morse Theory, Ergeb. Math. Grenzgeb., vol. 14 (1992), Springer: Springer Berlin
[14] Kozlov, D. N., Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes, in: Geometric Combinatorics, in: IAS/Park City Mathematics Series, vol. 14, American Mathematical Society/Institute for Advanced Study, Providence, RI/Princeton, NJ, in press · Zbl 1139.05022
[15] Kozlov, D. N., Collapsing along monotone poset maps, Preprint, 2005, 7 p. · Zbl 1179.06003
[16] Kozlov, D. N., A simple proof for folds on both sides in complexes of graph homomorphisms, Proc. Amer. Math. Soc., in press · Zbl 1081.05035
[17] Kozlov, D. N., Rational homology of spaces of complex monic polynomials with multiple roots, Mathematika, 49, 77-91 (2002) · Zbl 1065.58027
[18] Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25, 3, 319-324 (1978) · Zbl 0418.05028
[19] Vassiliev, V. A., Complexes of connected graphs, (The Gel’fand Mathematical Seminars 1990-1992 (1992), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 223-235 · Zbl 0812.55005
[20] Whitehead, J. H.C., Simplicial spaces, nuclei and \(m\)-groups, Proc. London Math. Soc., 45, 243-327 (1939) · Zbl 0022.40702
[21] Živaljević, R. T., WI-posets, graph complexes and \(Z_2\)-equivalences, Preprint, 2004, 20 p. · Zbl 1074.05091
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.