|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Complexes of graph homomorphisms | | Eric Babson
; Dmitry N. Kozlov
; | | Date: |
5 Oct 2003 | | Subject: | Combinatorics; Algebraic Topology MSC-class: 05C15; 55P91, 55S35, 57M15 | math.CO math.AT | | Abstract: | $Hom(G,H)$ is a polyhedral complex defined for any two undirected graphs $G$ and $H$. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that $Hom(K_m,K_n)$ is homotopy equivalent to a wedge of $(n-m)$-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graph $G$, and integers $mgeq 2$ and $kgeq -1$, we have $varpi_1^k( hom(K_m,G))
eq 0$, then $chi(G)geq k+m$; here $Z_2$-action is induced by the swapping of two vertices in $K_m$, and $varpi_1$ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of $Hom(G,H)$ induces a homotopy equivalence. It then follows that $Hom(F,K_n)$ is homotopy equivalent to a direct product of $(n-2)$-dimensional spheres, while $Hom(ar{F},K_n)$ is homotopy equivalent to a wedge of spheres, where $F$ is an arbitrary forest and $ar{F}$ is its complement. | | Source: | arXiv, math.CO/0310056 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER