Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free

2024/12/26 by Fujii, Soichiro, Kimura, Kei, Nozaki, Yuta · 1 citation
#05C15 (Primary) 55P15 #06A15 (Secondary) #55U05 #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2412.19039

Abstract

Given finite simple graphs G and H, the Hom complex Hom(G,H) is a polyhedral complex having the graph homomorphisms G→ H as the vertices. We determine the homotopy type of each connected component of Hom(G,H) when H is square-free, meaning that it does not contain the 4-cycle graph C₄ as a subgraph. Specifically, for a connected G and a square-free H, we show that each connected component of Hom(G,H) is homotopy equivalent to a wedge sum of circles. We further show that, given any graph homomorphism f\colon G→ H to a square-free H, one can determine the homotopy type of the connected component of Hom(G,H) containing f algorithmically.

Cited by

• Towards an algebraic approach to the reconfiguration CSP

Related

• Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles
• Hom complexes of graphs whose codomains are square-free
• The homotopy type of complexes of graph homomorphisms between cycles
• Simple S_r-homotopy types of Hom complexes and box complexes associated to r-graphs
• Hom complexes and homotopy theory in the category of graphs