Coloring using polynomials

Research Horizons Seminar
Wednesday, September 3, 2008 - 12:00
1 hour (actually 50 minutes)
Skiles 255
School of Mathematics, Georgia Tech
I will explain and prove a beautiful and useful theorem of Alon and Tarsi that uses multivariate polynomials to guarantee, under suitable hypotheses, the existence of a coloring of a graph. The proof method, sometimes called a Combinatorial Nullstellensatz, has other applications in graph theory, combinatorics and number theory.