
Hilbert's Nullstellensatz and Graph kcolorability.Michael Monagan, CECM.
Abstract: Given a graph G, we say G is kcolorable if we can assign each vertex one of k colors so that no two adjacent vertices have the same color. It is well known that the question "is G kcolorable" is NPcomplete for k>2. In 2008, de Loera, Lee, Peter Malkin and Susan Margulies presented a paper at ISSAC '08 showing how to convert the question Is G kcolorable into whether an ideal is trivial or not (this was already known), and secondly, how to convert that latter question into whether a linear system Ax=b has a solution modulo p different from k or not. The linear systems are large and sparse. What they found was a measure for how difficult the kcolorability of various graphs is. Whether this will lead to any real progress on the P = NP conjecture, they did not say. In the talk I would like to simply present their results. The connection between kcolorability, a combinatorial problem and ideal membership (is 1 in an ideal) is interesting. 