**UM Math Graduate Students Seminar**

Dr. Anton Dochtermann

*University of Miami*

**will present**

**Topology of colorings and graph homomorphisms **

Friday, February 3, 2012, 2:15pm

Ungar Building Room 402

**Abstract:**A 'proper coloring' of a graph G is an assignment of colors to the vertices of G such that adjacent vertices receive different colors (a special case of a more general notion of 'graph homomorphism'). The chromatic number of a graph G is the smallest number of colors needed to properly color G. Proving upper bounds on chromatic number is some sense easy (just exhibit a coloring) but in general lower bounds are hard to come by. In the 70s Lovasz studied a class of graphs defined in terms of intersecting subsets (known as 'Kneser graphs') and established a lower bound on their chromatic number (matching upper bounds were already known). His proof was surprising in that it employed basic notions of algebraic topology along the lines of the Borsuk-Ulam Theorem, and ushered in techniques which now come under the heading of 'topological combinatorics'. We'll discuss Lovasz's proof in the context of more contemporary 'homomorphism complexes' of graphs, and discuss extensions and the general theory that has emerged. In keeping with the theme of the seminar we'll at least mention Stiefel manifolds and characteristic classes.

Back to the seminar's page