MIT Combinatorics Seminar

Graph colorings and toric algebra

Dave Bayer  (Columbia University)

Wednesday, February 28, 2007    4:15 pm    Room 2-136


Analogous to the theory of conservative vector fields, vertex colorings of graphs can be represented up to constant by edge functions that sum to zero around every cycle. More generally, one can assign arbitrary real intervals to the edges of a graph, defining a box in the space of edge functions, and ask if any function in this box sums to an integer around every cycle. The chromatic number of a graph, and generalizations such as the circular chromatic number and the cyclic group chromatic number, can be determined by knowing which such integer programs are feasible. A dual theory applies to flows.

Following in a recent tradition of understanding integer programs through toric algebra, we relate the cycle and second cycle structure of a graph to the algebraic structure of a corresponding toric ring. An irreducible decomposition of this ring corresponds to the maximal lattice-free polytopes studied by Scarf et. al., which for us characterize the maximal infeasible integer programs on the graph. Chromatic information about the graph is encoded in the failure of the Cohen-Macaulay condition for this ring.

This is joint work with Maria Chudnovsky and Lindsay Piechnik.