Bay Area Discrete Math Day XII: The Coloring Torus of a...

Google TechTalks Bay Area Discrete Math Day XII April 15, 2006 Dave Bayer (Barnard College, Columbia University) ABSTRACT Circular colorability geometrizes the study of graph colorings. Using color values in R mod Z, one can reformulate "avoid edge differences close to zero" as " seek edge differences close to 1/2", then generalize to arbitrary edge difference goals. We define the coloring torus Xg of a graph G to be the space of all such coloring problems. X is made of the same stuff as the color values R mod Z: it is R mod L for a lattice L, so we can apply toric methods to its study. For planar graphs, the observed distances from 0 to torsion points of Xg form a pattern generalizing the four...