Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909770953261056 |
|---|---|
| author | Fujii, Soichiro Iwamasa, Yuni Kimura, Kei Nozaki, Yuta Suzuki, Akira |
| author_facet | Fujii, Soichiro Iwamasa, Yuni Kimura, Kei Nozaki, Yuta Suzuki, Akira |
| contents | For simple graphs $G$ and $H$, the Hom complex $\mathrm{Hom}(G,H)$ is a polyhedral complex whose vertices are the graph homomorphisms $G\to H$ and whose edges connect the pairs of homomorphisms which differ in a single vertex of $G$. Hom complexes play an important role in an algebro-topological approach to the graph coloring problem. It is known that $\mathrm{Hom}(G,H)$ is homotopy equivalent to a disjoint union of points and circles when both $G$ and $H$ are cycles. We generalize this known result by showing that the same holds whenever $G$ is connected and $H$ is a cycle. To this end, we explicitly construct the universal cover of each connected component of $\mathrm{Hom}(G,H)$ and prove that it is contractible. Additionally, we provide a simple criterion to determine whether the connected component containing a given homomorphism is homotopy equivalent to a point or circle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04802 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles Fujii, Soichiro Iwamasa, Yuni Kimura, Kei Nozaki, Yuta Suzuki, Akira Combinatorics Algebraic Topology 55U05, 05C15 (Primary) 55P15 (Secondary) For simple graphs $G$ and $H$, the Hom complex $\mathrm{Hom}(G,H)$ is a polyhedral complex whose vertices are the graph homomorphisms $G\to H$ and whose edges connect the pairs of homomorphisms which differ in a single vertex of $G$. Hom complexes play an important role in an algebro-topological approach to the graph coloring problem. It is known that $\mathrm{Hom}(G,H)$ is homotopy equivalent to a disjoint union of points and circles when both $G$ and $H$ are cycles. We generalize this known result by showing that the same holds whenever $G$ is connected and $H$ is a cycle. To this end, we explicitly construct the universal cover of each connected component of $\mathrm{Hom}(G,H)$ and prove that it is contractible. Additionally, we provide a simple criterion to determine whether the connected component containing a given homomorphism is homotopy equivalent to a point or circle. |
| title | Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles |
| topic | Combinatorics Algebraic Topology 55U05, 05C15 (Primary) 55P15 (Secondary) |
| url | https://arxiv.org/abs/2408.04802 |