Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911154336432128 |
|---|---|
| author | Fujii, Soichiro Kimura, Kei Nozaki, Yuta |
| author_facet | Fujii, Soichiro Kimura, Kei Nozaki, Yuta |
| contents | Given finite simple graphs $G$ and $H$, the Hom complex $\mathrm{Hom}(G,H)$ is a polyhedral complex having the graph homomorphisms $G\to H$ as the vertices. We determine the homotopy type of each connected component of $\mathrm{Hom}(G,H)$ when $H$ is square-free, meaning that it does not contain the $4$-cycle graph $C_4$ as a subgraph. Specifically, for a connected $G$ and a square-free $H$, we show that each connected component of $\mathrm{Hom}(G,H)$ is homotopy equivalent to a wedge sum of circles. We further show that, given any graph homomorphism $f\colon G\to H$ to a square-free $H$, one can determine the homotopy type of the connected component of $\mathrm{Hom}(G,H)$ containing $f$ algorithmically. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19039 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free Fujii, Soichiro Kimura, Kei Nozaki, Yuta Combinatorics Algebraic Topology 55U05, 05C15 (Primary) 55P15, 06A15 (Secondary) Given finite simple graphs $G$ and $H$, the Hom complex $\mathrm{Hom}(G,H)$ is a polyhedral complex having the graph homomorphisms $G\to H$ as the vertices. We determine the homotopy type of each connected component of $\mathrm{Hom}(G,H)$ when $H$ is square-free, meaning that it does not contain the $4$-cycle graph $C_4$ as a subgraph. Specifically, for a connected $G$ and a square-free $H$, we show that each connected component of $\mathrm{Hom}(G,H)$ is homotopy equivalent to a wedge sum of circles. We further show that, given any graph homomorphism $f\colon G\to H$ to a square-free $H$, one can determine the homotopy type of the connected component of $\mathrm{Hom}(G,H)$ containing $f$ algorithmically. |
| title | Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free |
| topic | Combinatorics Algebraic Topology 55U05, 05C15 (Primary) 55P15, 06A15 (Secondary) |
| url | https://arxiv.org/abs/2412.19039 |