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