Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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. In this talk I will survey the study of the Hom-complexes, and the ways these can be used to obtain lower bounds for the chromatic numbers of graphs.

The structural theory will be developed and put in the historical context, encompassing in particular the Lovasz 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$ and $k$, $r>0$, $k>-2$, we know that the chromatic number of $G$ is at least $k+4$.

Beyond the, more customary in this area, cohomology groups, the algebro-topological concepts involved are spectral sequences and Stiefel-Whitney characteristic classes. The latter are used to state the more general Babson-Kozlov conjecture which says:

For any graph $G$, we have $\chi(G)\geq h(Hom(C_{2r+1},G))+3$.

Here, for a ${\mathbb Z}_2$-space $X$, $h(X)$ denotes the maximal exponent of the non-zero power of the Stiefel-Whitney characteristic class of the associated line bundle.

I shall give an extremely short combinatorial proof of the Babson-Kozlov conjecture. Furthermore, I shall describe how to use the spectral sequences to perform a complete calculation of the cohomology groups of the colorings of cycles. If time permits, I will also say a few words about homological tests for graph colorings based on our theoretical results.

(part of the talk is based on joint work with Eric Babson and with Sonja Cukic)

Talk to the organizer soon if you are interested in dinner with the speaker.