First Groebner basis examples.
f1 := x*z-y^2; f2 := x^3-z^2; f := expand(2*x^2*f1+f1+3*f2);
LCYqJkkieEc2IiIiIkkiekdGJUYmRiYqJClJInlHRiUiIiNGJiEiIg==
LCYqJClJInhHNiIiIiQiIiJGKCokKUkiekdGJiIiI0YoISIi
LC4qKCIiIyIiIilJInhHNiIiIiRGJUkiekdGKEYlRiUqKEYkRiUpRidGJEYlKUkieUdGKEYkRiUhIiIqJkYnRiVGKkYlRiUqJEYtRiVGLyomRilGJUYmRiVGJSomRilGJSlGKkYkRiVGLw==
By construction, the polynomial f is in the ideal <f1,f2>.
with(Groebner);
NzpJJkJhc2lzRzYiSSVGR0xNR0YkSTFIaWxiZXJ0RGltZW5zaW9uR0YkSTJIaWxiZXJ0UG9seW5vbWlhbEdGJEkuSGlsYmVydFNlcmllc0dGJEksSW50ZXJSZWR1Y2VHRiRJKUlzUHJvcGVyR0YkSTJJc1plcm9EaW1lbnNpb25hbEdGJEkzTGVhZGluZ0NvZWZmaWNpZW50R0YkSTBMZWFkaW5nTW9ub21pYWxHRiRJLExlYWRpbmdUZXJtR0YkSS5Nb25vbWlhbE9yZGVyR0YkSTVNdWx0aXBsaWNhdGlvbk1hdHJpeEdGJEkrTm9ybWFsRm9ybUdGJEkqTm9ybWFsU2V0R0YkSSdSZWR1Y2VHRiRJLlJlbWVtYmVyQmFzaXNHRiRJLFNQb2x5bm9taWFsR0YkSSZTb2x2ZUdGJEkqVGVzdE9yZGVyR0YkSTBUb3JpY0lkZWFsQmFzaXNHRiRJNVVuaXZhcmlhdGVQb2x5bm9taWFsR0YkSSVXYWxrR0YkSSpmZ2xtX2FsZ29HRiQ=
LeadingTerm(f,tdeg(x,y,z)); LeadingTerm(f,plex(x,y,z)); LeadingTerm(f,plex(z,y,x));
NiQhIiMqJilJInhHNiIiIiMiIiIpSSJ5R0YnRihGKQ==
NiQiIiMqJilJInhHNiIiIiQiIiJJInpHRidGKQ==
NiQhIiQqJClJInpHNiIiIiMiIiI=
LeadingCoefficient(f,tdeg(x,y,z));
ISIj
LeadingMonomial(f,plex(x,y,z));
KiYpSSJ4RzYiIiIkIiIiSSJ6R0YlRic=
f1; f2;
LCYqJkkieEc2IiIiIkkiekdGJUYmRiYqJClJInlHRiUiIiNGJiEiIg==
LCYqJClJInhHNiIiIiQiIiJGKCokKUkiekdGJiIiI0YoISIi
SPolynomial( f1, f2, plex(x,y,z) );
LCYqJilJInhHNiIiIiMiIiIpSSJ5R0YmRidGKCEiIiokKUkiekdGJiIiJEYoRig=
S12 := expand( x^2*f1-z*f2 );
LCYqJilJInhHNiIiIiMiIiIpSSJ5R0YmRidGKCEiIiokKUkiekdGJiIiJEYoRig=
NormalForm( S12, [f1,f2], plex(x,y,z) );
LCYqJilJInhHNiIiIiMiIiIpSSJ5R0YmRidGKCEiIiokKUkiekdGJiIiJEYoRig=
G1 := Basis([f1,f2],plex(x,y,z));
NycsJiokKUkieUc2IiIiJyIiIkYpKiQpSSJ6R0YnIiImRikhIiIsJiomSSJ4R0YnRilGLEYpRikqJClGJiIiI0YpRi4sJiomKUYmIiIlRilGMUYpRikqJClGLEY4RilGLiwmKiYpRjFGNEYpRjNGKUYpKiQpRiwiIiRGKUYuLCYqJClGMUZARilGKSokKUYsRjRGKUYu
G2 := Basis([f1,f2],tdeg(x,y,z));
NyQsJiomSSJ4RzYiIiIiSSJ6R0YmRichIiIqJClJInlHRiYiIiNGJ0YnLCYqJClGJSIiJEYnRicqJClGKEYtRidGKQ==
Verify that f is in the ideal <f1,f2>
NormalForm(f,G1,plex(x,y,z));
IiIh
NormalForm(f,G2,tdeg(x,y,z));
IiIh
The graph k-coloring examples. This is the graph for the cycle on n=5 vertices V
n := 3; V := [1,2,3,4,5]; E := {{1,2},{2,3},{3,4},{4,5},{5,1}};
IiIk
NyciIiIiIiMiIiQiIiUiIiY=
PCc8JCIiIyIiJDwkIiIiRiQ8JEYlIiIlPCRGKSIiJjwkRidGKw==
k := 2; # try two colors
IiIj
S := {seq( x[v]^k+1, v=V )};
PCcsJiokKSZJInhHNiI2IyIiIiIiI0YqRipGKkYqLCYqJCkmRic2I0YrRitGKkYqRipGKiwmKiQpJkYnNiMiIiRGK0YqRipGKkYqLCYqJCkmRic2IyIiJUYrRipGKkYqRiosJiokKSZGJzYjIiImRitGKkYqRipGKg==
Eeqns := proc(e) local u,v;
u,v := op(e); normal( (x[u]^k-x[v]^k)/(x[u]-x[v]) )
end;
Zio2I0kiZUc2IjYkSSJ1R0YlSSJ2R0YlRiVGJUMkPkYmLUkjb3BHJSpwcm90ZWN0ZWRHRiMtSSdub3JtYWxHRi02IyomLCYpJkkieEdGJTYjRidJImtHRiUiIiIpJkY1NiNGKEY3ISIiRjgsJkY0RjhGOkY8RjxGJUYlRiU=
Eeqns(E[1]);
LCYmSSJ4RzYiNiMiIiMiIiImRiQ2IyIiJEYo
S := S union {seq( Eeqns(e), e=E )};
PCwsJiokKSZJInhHNiI2IyIiIiIiI0YqRipGKkYqLCYqJCkmRic2I0YrRitGKkYqRipGKiwmKiQpJkYnNiMiIiRGK0YqRipGKkYqLCYqJCkmRic2IyIiJUYrRipGKkYqRiosJiokKSZGJzYjIiImRitGKkYqRipGKiwmRi9GKkY0RiosJkYmRipGL0YqLCZGNEYqRjpGKiwmRjpGKkZARiosJkYmRipGQEYq
X := seq( x[v], v=V );
NicmSSJ4RzYiNiMiIiImRiQ2IyIiIyZGJDYjIiIkJkYkNiMiIiUmRiQ2IyIiJg==
Basis( S, plex(X) );
NyMiIiI=
Thus the graph G is not 2-colorable
k := 3;
S := {seq( x[v]^k+1, v=V )} union {seq( Eeqns(e), e=E )};
IiIk
PCwsKCokKSZJInhHNiI2IyIiIiIiI0YqRioqJiZGJzYjRitGKkYmRipGKiokKUYtRitGKkYqLChGJEYqKiYmRic2IyIiJkYqRiZGKkYqKiQpRjNGK0YqRiosKCokKSZGJzYjIiIkRitGKkYqKiZGO0YqJkYnNiMiIiVGKkYqKiQpRj9GK0YqRiosJiokKUY/Rj1GKkYqRipGKiwmKiQpRjNGPUYqRipGKkYqLChGL0YqKiZGLUYqRjtGKkYqRjlGKiwoRkJGKiomRj9GKkYzRipGKkY2RiosJiokKUYmRj1GKkYqRipGKiwmKiQpRi1GPUYqRipGKkYqLCYqJClGO0Y9RipGKkYqRio=
Basis( S, plex(X) );
NyksJiokKSZJInhHNiI2IyIiJiIiJCIiIkYsRixGLCwoKiQpJkYnNiMiIiUiIiNGLEYsKiZGMEYsRiZGLEYsKiQpRiZGM0YsRiwsKkY1ISIiRjRGOCokKSZGJzYjRitGM0YsRiwqJkY7RixGMEYsRiwsLCokKSZGJzYjRjNGM0YsRixGNUYsRjRGLComRkFGLEY7RixGLEY9RjgsNComRjtGLCZGJzYjRixGLEYsRjVGLEY0RiwqJkY7RixGJkYsRiwqJkYwRixGRkYsRiwqJkYmRixGRkYsRixGQ0YsKiZGQUYsRjBGLEYsKiZGQUYsRiZGLEYsLC4qJkZBRixGRkYsRixGNEY4KiZGM0YsRjZGLEY4RkpGOEZDRjhGPUYsLCgqJClGRkYzRixGLEZKRixGNUYs
Since the GB is not [1] then S is 3-colorable. The colorings are given by the solutions. We could solve them.
n := 8;
V := [$1..8];
E := {{1,2},{1,6},{1,5},{2,3},{2,4},{2,8},{3,4},{3,8},{4,5},{4,7},{5,7},{6,7},{7,8},{5,6}};
IiIp
NyoiIiIiIiMiIiQiIiUiIiYiIiciIigiIik=
PDA8JCIiIyIiJDwkIiIiRiQ8JEYlIiIlPCRGKSIiJjwkRidGKzwkRiciIic8JEYkRik8JEYkIiIpPCRGJUYxPCRGKSIiKDwkRitGNDwkRi5GNDwkRjRGMTwkRitGLg==
m := nops(E);
IiM5
X := seq( x[v], v=V );
NiomSSJ4RzYiNiMiIiImRiQ2IyIiIyZGJDYjIiIkJkYkNiMiIiUmRiQ2IyIiJiZGJDYjIiInJkYkNiMiIigmRiQ2IyIiKQ==
k := 3; S := {seq( x[v]^k+1, v=V )} union {seq( Eeqns(e), e=E )};
IiIk
PDgsKCokKSZJInhHNiI2IyIiIiIiI0YqRioqJiZGJzYjRitGKkYmRipGKiokKUYtRitGKkYqLChGJEYqKiYmRic2IyIiJkYqRiZGKkYqKiQpRjNGK0YqRiosKCokKSZGJzYjIiIlRitGKkYqKiYmRic2IyIiKEYqRjtGKkYqKiQpRj9GK0YqRiosKCokKSZGJzYjIiIkRitGKkYqKiZGR0YqRjtGKkYqRjlGKiwmKiQpRjtGSUYqRipGKkYqLCYqJClGM0ZJRipGKkYqRiosKEYvRioqJkYtRipGR0YqRipGRUYqLChGOUYqKiZGO0YqRjNGKkYqRjZGKiwoRjZGKiomJkYnNiMiIidGKkYzRipGKiokKUZXRitGKkYqLCYqJClGJkZJRipGKkYqRiosJiokKUYtRklGKkYqRipGKiwmKiQpRkdGSUYqRipGKkYqLCYqJClGV0ZJRipGKkYqRiosJiokKUY/RklGKkYqRipGKiwmKiQpJkYnNiMiIilGSUYqRipGKkYqLChGJEYqKiZGV0YqRiZGKkYqRlpGKiwoRi9GKiomRi1GKkY7RipGKkY5RiosKEYvRioqJkZob0YqRi1GKkYqKiQpRmhvRitGKkYqLChGRUYqKiZGaG9GKkZHRipGKkZhcEYqLChGNkYqKiZGP0YqRjNGKkYqRkJGKiwoRlpGKiomRj9GKkZXRipGKkZCRiosKEZCRioqJkZob0YqRj9GKkYqRmFwRio=
G := Basis(S,tdeg(X));
NyosJiZJInhHNiI2IyIiJyIiIiZGJTYjIiIpISIiLCgmRiU2IyIiJkYpRipGKSZGJTYjIiIoRiksJiZGJTYjIiIlRilGKkYtLCZGMkYtJkYlNiMiIiRGKSwoJkYlNiMiIiNGKUYyRilGKkYpLCYmRiU2I0YpRilGMkYtLCgqJClGMkZARilGKSomRipGKUYyRilGKSokKUYqRkBGKUYpLCYqJClGKkY8RilGKUYpRik=
_EnvExplicit := true;
SSV0cnVlRyUqcHJvdGVjdGVkRw==
The six solutions tell us that there are six color assignments for the vertices.
sols := solve( {op(G)}, {X} );
Nig8Ki8mSSJ4RzYiNiMiIikhIiIvJkYmNiMiIidGKi8mRiY2IyIiJUYqLyZGJjYjIiIoLCYjIiIiIiIjRjkqJiomRjhGOV4jRjlGOUY5KSIiJEY4RjlGOS8mRiY2IyIiJiwmRjhGOSomLCRGPEY5RjlGPkY5RiovJkYmNiNGP0Y3LyZGJjYjRjpGRC8mRiY2I0Y5Rjc8KkYkRitGLy9GQUY3L0ZLRjcvRk5GRC9GSEZEL0Y0RkQ8Ki9GNEYqL0ZIRiovRk5GKkZARkovRiVGNy9GLEY3L0YwRjc8KkZXRlhGWUZRRlIvRiVGRC9GLEZEL0YwRkQ8Ki9GQUYqL0ZLRipGU0ZURlVGWkZlbkZmbjwqRlxvRl1vRjNGR0ZNRmhuRmluRmpu
The colors are the roots of unity, i.e., -1, 1/2+-NiMqJiUiaUciIiItJSVzcXJ0RzYjIiIkRiU= /2.
sols := subs( {1/2+sqrt(3)*I/2=red, 1/2-sqrt(3)*I/2=blue, -1=green}, [sols] );
Nyg8Ki8mSSJ4RzYiNiMiIilJJmdyZWVuR0YnLyZGJjYjIiInRiovJkYmNiMiIiVGKi8mRiY2IyIiKEkkcmVkR0YnLyZGJjYjIiImSSVibHVlR0YnLyZGJjYjIiIkRjcvJkYmNiMiIiNGPC8mRiY2IyIiIkY3PCpGJEYrRi8vRjlGNy9GQkY3L0ZGRjwvRj5GPC9GNEY8PCpGOEZBL0Y0RiovRj5GKi9GRkYqL0YlRjcvRixGNy9GMEY3PCpGSkZLRlBGUUZSL0YlRjwvRixGPC9GMEY8PCpGTEZNRk5GU0ZURlUvRjlGKi9GQkYqPCpGM0Y9RkVGV0ZYRllGZW5GZm4=
This is just to show off our new Graph theory package.
currentdir("/home/mmonagan/GraphTheory/GTv25");
UTovaG9tZS9tbW9uYWdhbi9NQVRINDMyLzA2NiI=
read "GTv25.mpl";
G := Graph(V,E);
LUkoR1JBUEhMTkclKnByb3RlY3RlZEc2KEkrdW5kaXJlY3RlZEdGJEkrdW53ZWlnaHRlZEdGJDcqIiIiIiIjIiIkIiIlIiImIiInIiIoIiIpLUkmQXJyYXlHRiQ2Iy9JJCVpZEc2IiIoKVtcYEkwR1JBUEhMTi90YWJsZS8xR0Y2IiIh
coloring := sols[1];
PCovJkkieEc2IjYjIiIpSSZncmVlbkdGJi8mRiU2IyIiJ0YpLyZGJTYjIiIlRikvJkYlNiMiIihJJHJlZEdGJi8mRiU2IyIiJkklYmx1ZUdGJi8mRiU2IyIiJEY2LyZGJTYjIiIjRjsvJkYlNiMiIiJGNg==
HighlightVertex(G,[1,3,7],red);
HighlightVertex(G,[2,5],blue);
HighlightVertex(G,[4,6,8],green);
DrawGraph(G);
NjstSSlQT0xZR09OU0c2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYsNyY3JCQiKyoqKioqZkYmISM1JCIrKytnRjUhIio3JEYsJCIrKysrQygqRi43JCQiKyoqKioqUnMlRi5GMzckRjZGLzcmNyQkIiswUmA2KSlGLkY7NyRGOyQiKzBSYGYjKUYuNyRGPkY+NyRGPkY7NyY3JEYvJCIrKysrd19GLjckRi8kIisrKytDWkYuNyRGM0ZHNyRGM0ZENyY3JEY7JCIrJTRtL3UiRi43JEY7JCIrJTRtJSk9IkYuNyRGPkZQNyRGPkZNNyY3JEYsJCIrKysrZ0YhIzY3JEYsJCErKysrZ0ZGWDckRjZGWjckRjZGVjcmNyRGTUZNNyRGTUZQNyRGUEZQNyRGUEZNNyY3JEZWRkQ3JEZWRkc3JEZaRkc3JEZaRkQ3JjckJCIrKTRtL3UiRi4kIis1UmA2KSlGLjckRmRvJCIrNVJgZiMpRi43JCQiKyk0bSUpPSJGLkZpbzckRlxwRmZvLUkmQ09MT1JHRiU2O0kkUkdCR0YlJCIqKysrKyIhIikkIiIhRmdwRmZwRmZwRmZwRmNwRmNwRmZwRmZwRmZwRmNwRmZwRmZwRmZwRmNwRmZwRmNwRmZwRmNwRmZwRmZwRmZwRmNwRmZwLUkmU1RZTEVHRiU2I0ksUEFUQ0hOT0dSSURHRiUtSSVURVhUR0YlNiU3JCQiKyoqKioqKioqXEYuJCIjNSEiIlEiMUYoLUklRk9OVEdGKDYlSSpIRUxWRVRJQ0FHRihJJUJPTERHRigiIzctRl1xNiU3JCQiKzBSYE4mKUYuRl9yUSIyRihGZnEtRl1xNiU3JEZicSQiIiZGZHFRIjNGKEZmcS1GXXE2JTckRl9yJCIrJTRtV1kiRi5RIjRGKEZmcS1GXXE2JTckRmBxRmZwUSI1RihGZnEtRl1xNiU3JEZbc0Zbc1EiNkYoRmZxLUZdcTYlNyRGZnAkIisrKysrXUYuUSI3RihGZnEtRl1xNiU3JCQiKyk0bVdZIkYuJCIrNVJgTiYpRi5RIjhGKEZmcS1GJDYmNyRGXnJGX3EtRmBwNiZGYnBGZ3BGZ3AiIiItSSpUSElDS05FU1NHRiU2IyIiIy1GaXA2I0klTElORUdGJS1GJDYmNyRGZHJGXnJGZ3RGanRGXnUtRiQ2JjckRmpyRl5yRmd0Rmp0Rl51LUYkNiY3JEZqckZkckZndEZqdEZedS1GJDYmNyRGYHNGX3FGZ3RGanRGXnUtRiQ2JjckRmBzRmpyRmd0Rmp0Rl51LUYkNiY3JEZkc0ZfcUZndEZqdEZedS1GJDYmNyRGZHNGYHNGZ3RGanRGXnUtRiQ2JjckRmhzRmpyRmd0Rmp0Rl51LUYkNiY3JEZoc0Zgc0ZndEZqdEZedS1GJDYmNyRGaHNGZHNGZ3RGanRGXnUtRiQ2JjckRl50Rl5yRmd0Rmp0Rl51LUYkNiY3JEZedEZkckZndEZqdEZedS1GJDYmNyRGXnRGaHNGZ3RGanRGXnUtSShTQ0FMSU5HR0YoNiNJLENPTlNUUkFJTkVER0YlLUkqQVhFU1NUWUxFR0YlNiNJJU5PTkVHRiU=