Michael Monagan, April 2010.
The following calculations illustrate the ideas in the paper "Graph k-Colorability and Hilbert's NSS" by Margulies et. al.with(GraphTheory):Wn := proc(n)
#Graph( [seq(i,i=0..n)],
# {seq( {0,i}, i=1..n ), seq( {i,i+1}, i=1..n-1 ), {n,1}} )
SpecialGraphs:-WheelGraph(n);
end:W5 := Wn(5);DrawGraph(W5);P := SpecialGraphs:-PetersenGraph();DrawGraph(P);The Petersen graph is 3 colorable.IsVertexColorable(P,3,'C');C;HighlightVertex(P,C[1],red);HighlightVertex(P,C[2],green);DrawGraph(P);Create the system of equations.Sys := proc(G::Graph,x::name,k::nonnegint)
local V,E,v,e,S;
V,E := Vertices(G), Edges(G);
S := {seq( x[v]^k-1, v=V )} union
{seq( normal( (x[e[1]]^k-x[e[2]]^k) / (x[e[1]]-x[e[2]]) ), e=E )}
end: S := Sys( Wn(3), x, 3 );S := subs( x[0]=1, S ): # assign vertex 0 to be one of the colorsGroebner[Basis]( S, tdeg(x[0],x[1],x[2],x[3]) ); S := Sys( Wn(4), x, 3 );S := subs( x[0]=1, S );Groebner[Basis](S, tdeg(x[1],x[2],x[3],x[4]) );Monomials := proc(X::set(name),d::nonnegint) option remember; local x,i,m;
# return all monomials in X of degree 0,1,...,d .
if X={} then return 1 fi;
x := X[1];
seq( seq( x^i*m, m=Monomials( X[2..-1], d-i ) ), i=0..d );
end:Monomials( {x,y,z}, 3 );HNSS := proc( S::set(polynom), d::nonnegint, c::name, ansatz::name )
local M,i,one,X;
X := indets(S,name); #print(X);
M := [Monomials(X,d)]; #print(M);
one := add( add( c[i,j]*M[j], j=1..nops(M) )*S[i], i=1..nops(S) );
if nargs=4 then ansatz := one fi;
{ coeffs( expand(one)-1, X ) };
end:S := HNSS( Sys(Wn(3),x,3), 1, c ); Try to find a degree 1 certificate for W(3)nops(S);nops( indets(S) );solve(S);S := HNSS( Sys(Wn(3),x,3), 2, c ): A degree 2 certificatenops(S);nops( indets(S) );solve(S);S := HNSS( Sys(Wn(3),x,3), 3, c ):A degree 3 certificatenops(S);nops(indets(S));solve(S);S := HNSS( Sys(Wn(3),x,3), 4, c, 'ZZ' ):A degree 4 certificatenops(S);nops(indets(S));sol := solve(S);Certificate := proc(ansatz, sol, c) local p;
p := map( proc(e) if lhs(e)=rhs(e) then lhs(e)=1 fi end, sol );
subs( p, subs( sol, ansatz ) );
end:Certificate( ZZ, sol, c );expand(%);Sys(Wn(3),x,3);S := HNSS( Sys(Wn(3),x,3), 1, c, 'ZZ' ); But a degree 1 certificate exists modulo 2 !!sol := msolve( S, 2 );Zvals := map( proc(e) if type(rhs(e),name) then rhs(e) fi end, sol );one := subs( {seq( z=1, z=Zvals)}, subs( sol, ZZ ) ) mod 2;Expand(%) mod 2;G := Graph( Trail(1,2,3,10,9,8,7,6,5,12,11,10,9,4,1),
Trail(1,6,10,9,5,12,8,7,11),
Trail(1,12,5,6,1,2,5,6,2,7,8,3,10,9,4,11) );P := [10=[1,0],9=[2,0],8=[3,1],7=[3,2],6=[2,3],5=[1,3],12=[0,2],11=[0,1],4=[-1,-1],1=[-1,4],2=[4,4],3=[4,-1]];SetVertexPositions(G,subs(P,[$1..12]));DrawGraph(G);IsVertexColorable(G,3);Triangles := {{1,2,6}, {2,5,6}, {2,6,7}};TEQN := map( proc(t) x[t[1]]^2+x[t[2]]^2+x[t[3]]^2 end, Triangles );Sys(G,x,3);for d from 1 do
sys := HNSS( Sys(G,x,3) union TEQN, d, c );
print(d,nops(sys));
sol := msolve(sys,2);
if sol <> NULL then print(good); break; fi
od:AHNSS := proc( S::set(polynom), d::nonnegint, c::name, ansatz::name, monom )
local M,i,one,X;
X := indets(S,name); print(X);
M := [Monomials(X,d)]; #print(M);
one := add( add( c[i,j]*M[j], j=1..nops(M) )*S[i], i=1..nops(S) );
if nargs>3 then ansatz := one fi;
{ coeffs( expand(one) - monom, X ) };
end:Try the alternative HNSS with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2JVEiZ0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj1GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1JJW1zdWJHRiQ2JS1GLDYlUSJ4RidGL0YyLUYjNiUtSSNtbkdGJDYkUSIxRidGOUYvRjIvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJy1GNjYtUScmc2RvdDtGJ0Y5RjtGPkZARkJGREZGRkgvRktRJjAuMGVtRicvRk5GXG8tRlA2JUZSLUYjNiUtRlg2JFEiOEYnRjlGL0YyRmVuRmhuLUZQNiVGUi1GIzYlLUZYNiRRIjlGJ0Y5Ri9GMkZlbkY5 .for d from 1 do
sys := AHNSS( Sys(G,x,3) union TEQN, d, c, 'ZZ', x[1]*x[8]*x[9] );
printf("degree=%d #eqns=%d \134n",d,nops(sys));
sol := msolve(sys,2);
if sol <> NULL then printf("degree %d certificant found\134n",d); break; fi
od:Certificate := proc(ansatz, sol, c) local p;
p := map( proc(e) if type(rhs(e),name) then rhs(e)=1 fi end, sol );
subs( p, subs( sol, ansatz ) );
end:Certificate( ZZ, sol ) mod 2;Expand(%) mod 2;