MATH 819 course project (10% of grade) Spring 2014.
Demo by Wednesday April 16th.  Due Wednesday April 23rd at 11am.
Late penalty -20% for up to 24 hours late.  Zero after that.

The goal of this project is to explore the Nullstellensatz
and apply it to proving graphs are not k-colorable.
Read the paper "Hilbert's Nullstellensatz and an Algorithm for 
Proving Combinatorial Infeasibility by Margulies et. al."

Implement a Maple code (can be one or more procedures)
for testing if a graph G is not k-colorable.  If you use a Maple
graph to represent the graph, the commands Vertices(G) and Edges(G)
will give you the vertices and edges.
To solve a linear system over Q use the solve( { e1, e2, ... } );
command.  Test your code on W3 the wheel graph with 3 vertices.
You can use the code in the (.pdf) file
Graph Coloring and Hilbert's Nullstellenstatz (.mw) and (.pdf)
on the course website for this.

Section 3.1 says that to test 3-colorability we can work
over the finite field F2 (the integers modulo 2).
The proof of Lemma 3.1 is wrong because it doesn't
capture why we can work over F2 but not over F3.
Why can't we test 3-colorability over F3?
Why can't we test 4-colorability over F2?
When can we test k-colorability over Fp?
Now fix the proof of Lemma 3.1.
  
At the end of 3.1 the authors say every odd-wheel graph
has a Nullstellensatz certificate of degree 1 but they give
no proof.  Presumably they just tried it for n=3,5,7,...
Verify it for n=3,5,7,...,13.
Do you see any pattern in the certificates that would allow
us to prove that a degree 1 certificate always exists?
Note, to solve a linear system over the integers modulo p use
   msolve( { e1, e2, ... }, p )

Section 3.2 has an example of a Koester graph and the authors 
claim that by adding equations for triangles they can find a
degree 1 Nullstellensatz certificate (over F2).  Verify this.
Now, if you use the equation x+y+z=0 instead of x^2+y^2+z^2=0
do you still get a degree 1 certificate?  
Verify for the graph in Figure 2 that it has no degree
1,2,3 certificate over F2.

Section 3.4 suggests an alternative Nullstellensatz.
The authors state Corollary 3.7 (Alternative Nullstellensatz) without
proof.  I think we need a proof to see which g(x) can be used and why.
For the graph in Figure 2 find a g(x) such that the Nullstellensatz
certificate has degree 1.
Note, to solve Ax1=b1, Ax2=b2, Ax2=b3, Ax=bm efficiently, i.e. at the
same time, row reduce [A|b1 b2 ... ] to [I|x1 x2 ... ].
To do this you can set up the matrix and execute
Gaussjord(A) mod p;