Algebraic Combinatorics Seminar
UNIVERSITY OF KENTUCKY
ALGEBRAIC COMBINATORICS SEMINAR
845 PATTERSON OFFICE TOWER
MASTERS EXAM TALK
"Complexes of t-colorable graphs"
University of Kentucky
Wednesday, April 19, 2006
4:00 pm, 845 Patterson Office Tower
We say a graph is t-colorable if one can assign one of t colors to
each vertex of the graph such that no adjacent vertices have the same
color. Since any subgraph of a t-colorable graph is t-colorable, the
set of all t-colorable graphs on a fixed vertex set can be considered
an abstract simplicial complex with the t-colorable graphs as faces.
In their 2003 paper "Complexes of t-colorable graphs", Svante Linusson
and John Shareshian apply the techniques of discrete Morse theory to
the complex of t-colorable graphs on the fixed vertex set [n] to
determine the homotopy type for t leq 2 and leq n-3. We will begin by
giving a brief introduction to the combinatorial description (due to
M. K. Chari) of Robin Forman's discrete Morse theory. We will then
present the proof of Linusson and Shareshian's result for 2-colorable
(bipartite) graphs and indicate how this same strategy can be applied
to obtain the remaining results.