Proof of the Lovasz Conjecture
| dc.creator | Babson, Eric | |
| dc.creator | Kozlov, Dmitry N. | |
| dc.date | 2004-02-24 | |
| dc.date | 2005-07-18 | |
| dc.date.accessioned | 2026-07-07T06:27:07Z | |
| dc.date.available | 2026-07-07T06:27:07Z | |
| dc.description | To any two graphs G and H one can associate a cell complex Hom(G,H) by taking all graph multihomorphisms from G to H as cells. In this paper we prove the Lovasz Conjecture which states that if Hom(C_{2r+1},G) is k-connected, then χ(G)\geq k+4, where r,k\in Z, r\geq 1, k\geq -1, and C_{2r+1} denotes the cycle with 2r+1 vertices. The proof requires analysis of the complexes Hom(C_{2r+1},K_n). For even n, the obstructions to graph colorings are provided by the presence of torsion in H^*(Hom(C_{2r+1},K_n);Z). For odd n, the obstructions are expressed as vanishing of certain powers of Stiefel-Whitney characteristic classes of Hom(C_{2r+1},K_n), where the latter are viewed as $\zz$-spaces with the involution induced by the reflection of C_{2r+1}. | |
| dc.description | Revised and updated version | |
| dc.identifier | https://arxiv.org/abs/math/0402395 | |
| dc.identifier | http://arxiv.org/abs/math/0402395 | |
| dc.identifier | Annals of Mathematics, submitted 2/2/2004, accepted 28/7/2005, http://www.math.princeton.edu/~annals/issues/2005/AnnalsAcceptedPapers2005.pdf | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/97324 | |
| dc.subject | Combinatorics | |
| dc.subject | Algebraic Topology | |
| dc.subject | 05C15; 57M15 | |
| dc.title | Proof of the Lovasz Conjecture | |
| dc.type | text |