Abstract
It is shown that given a connected graph T with at least one edge and an arbitrary finite simplicial complex X, there is a graph G such that the complex Hom(T,G) is homotopy equivalent to X. The proof is constructive, and uses a nerve lemma. Along the way several results regarding Hom complexes, exponentials of graphs, and subdivisions are established that may be of independent interest.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anders Björner: Topological methods, in: Handbook of combinatorics, Vol. 1, 2, pages 1819–1872, Elsevier, Amsterdam, 1995.
Eric Babson and Dmitry N. Kozlov: Complexes of graph homomorphisms, Israel J. Math.152 (2006), 285–312.
Eric Babson and Dmitry N. Kozlov: Proof of the Lovász Conjecture, Annals of Mathematics165(3) (2007), 965–1007.
Graham R. Brightwell and Peter Winkler: Graph homomorphisms and long range action, in: Graphs, morphisms and statistical physics, volume 63 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 29–47. Amer. Math. Soc., Providence, RI, 2004.
Péter Csorba: Homotopy types of box complexes, Combinatorica27(6) (2007), 669–682.
Anton Dochtermann: Hom complexes and homotopy theory in the category of graphs, European J. Combin.30(2) (2009), 490–509.
Dmitry N. Kozlov: Collapsing along monotone poset maps, Int. J. Math. Math. Sci.2006 (2006), Art. ID 79858, 8 pages.
Dmitry N. Kozlov: Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes; in: Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pages 249–315, Amer. Math. Soc., Providence, RI, 2007.
László Lovász: Kneser’s conjecture, chromatic number, and homotopy; J. Combin. Theory Ser. A25(3) (1978), 319–324.