The universality of Hom complexes of graphs

DOI10.1007/S00493-009-2376-7MaRDI QIDQ987561zbMATH OpenOpenAlexFDO

Authors Anton Dochtermann

Publication date 13 August 2010

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0702471

zbMATH Keywords

clique complexexponentials of graphsgraphHom complexes of graphshomotopy equivalencesubdivisions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of simplicial complexes (05E45) Classification of homotopy type (55P15) Relations of low-dimensional topology with graph theory (57M15)

Abstract: It is shown that if T is a connected nontrivial graph and X is an arbitrary finite simplicial complex, then 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, and subdivision are established that may be of independent interest.

Review text

The Hom complex is a functional way to assign a poset (and hence a topological space) Hom\((T,G)\) to a pair of graphs \(T\) and \(G\). P. Csorba proved that any free \(\mathbb Z_2\)-space can be realized, up to \(\mathbb Z_2\)-homotopy type, as Hom\((K_2,G)\) for some suitably chosen graph \(G\) (here \(K_2\) is an edge) [see \textit{P. Csorba}, Combinatorica 27, No. 6, 669--682 (2007; Zbl 1236.05067)]. A natural question is to ask what homotopy types can be realized as Hom\((T,?)\) for other test graphs \(T\). The author proves 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\). Other results on Hom complexes, exponentials of graphs, and subdivisions complete the paper.

Recommendations

• Complexes of graph homomorphisms
• Homotopy types of the Hom complexes of graphs
• Hom complexes and homotopy theory in the category of graphs
• Box complexes and homotopy theory of graphs
• Homology of \(\operatorname{Hom}\) complexes

Cites work

• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Collapsing along monotone poset maps
• Complexes of graph homomorphisms
• Hom complexes and homotopy theory in the category of graphs
• Homotopy types of box complexes
• scientific article; zbMATH DE number 2151248 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• Proof of the Lovász conjecture

Cited in

(30)

• Homotopy groups of Hom complexes of graphs
• Simplicial simple-homotopy of flag complexes in terms of graphs
• Realization of Hölder complexes
• Box complexes and homotopy theory of graphs
• Topology of Hom complexes and test graphs for bounding chromatic number
• Hom complexes of set systems
• A universal exponent for homeomorphs
• Families of nested graphs with compatible symmetric-group actions
• Complexes of graph homomorphisms
• Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes
• Affine hom-complexes
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Graph cores via universal completability
• scientific article; zbMATH DE number 5704224 (Why is no real title available?)
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• Clique complexes and graph powers
• scientific article; zbMATH DE number 13159 (Why is no real title available?)
• Homeomorphism of 2-Complexes is Graph Isomorphism Complete
• A Fixed Point Theorem for Groups Acting on Finite 2-Dimensional Acyclic Simplicial Complexes
• Homology of \(\operatorname{Hom}\) complexes
• Paths of homomorphisms from stable Kneser graphs
• Hom complexes and homotopy in the category of graphs
• Small Flag Complexes with Torsion
• Homomorphism and Dimension
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• The equivariant topology of stable Kneser graphs
• Hom complexes of graphs whose codomains are square-free
• Box complexes: at the crossroad of graph theory and topology
• Dissections, Hom-complexes and the Cayley trick
• Set partition complexes

This page was built for publication: The universality of Hom complexes of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987561)