|
Hilbert's Nullstellensatz and Graph k-colorability.Michael Monagan, CECM.
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. |