Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
Abstract
Description
Combinatorics, in particular graph theory, has a rich history of being a domain of successful applications of tools from other areas of mathematics, including topological methods. Here, we survey the study of the Hom-complexes, and the ways these can be used to obtain lower bounds for the chromatic numbers of graphs, presented in a recent series of papers \cite{BK03a,BK03b,BK03c,CK1,CK2,K4,K5}.
The structural theory is developed and put in the historical context, culminating in the proof of the Lovász Conjecture, which can be stated as follows:
For a graph G, such that the complex Hom(C_{2r+1},G) is k-connected for some integers r>0 and k>-2, we have χ(G)>k+3.
Beyond the, more customary in this area, cohomology groups, the algebro-topological concepts involved are spectral sequences and Stiefel-Whitney characteristic classes. Complete proofs are included for all the new results appearing in this survey for the first time.
Survey article for the Proceedings volume of the Institute for Advanced Study (Princeton). Complete proofs are included for all results appearing here for the first time
Survey article for the Proceedings volume of the Institute for Advanced Study (Princeton). Complete proofs are included for all results appearing here for the first time