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

Posted in Conferences, Companies, Science on December 30, 2006


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

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 color theorem. «

Watch Video

Tags: Techtalks, Google, Conferences, Science, Lectures, Math, Broadcasting, Companies