Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Coloring the vertices of a graph with no adjacent vertices in the same color, is an old problem in combinatorics. Most sufficient conditions are of local character, for example three colors in enough for a cycle since the maximal degree is two. But necessary conditions tend to be global: we need to know if the cycle have an even or odd number of vertices to determine if two or three colors are necessary. For graphs with more involved symmetries and parity questions than in cycles, the most efficient tool is a translation from the graph theory into algebra where the best tools for that are. I will first sketch this setup and describe how it was used by Lovasz to find the chromatic numbers for Kneser graphs. Then I will, in a very speculative manner, describe a program for how to use Groebner bases and toric geometry to attack coloring questions. Simple examples are demonstrated, and accessible research questions for grad students in combinatorics and commutative algebra are presented.