Hilbert's Nullstellensatz and Graph k-colorability.

Michael Monagan, CECM.


Wednesday February 18th, 3:30pm, in K9509.


Abstract: 

Given a graph G, we say G is k-colorable 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 k-colorable" is NP-complete 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 k-colorable 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 k-colorability 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 k-colorability, a combinatorial problem and 
ideal membership (is 1 in an ideal) is interesting.