{VERSION 6 0 "IBM INTEL LINUX" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "First Groebner basis examp les" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "f1 := x*z-y^2; f2 := x^3-z^2; f := expand(2*x^2*f1+f1+3*f2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,&*&%\"xG\"\"\"%\"zGF(F(*$)%\"yG\"\"#F(!\"\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#f2G,&*$)%\"xG\"\"$\"\"\"F**$)%\"zG\"\"#F*!\" \"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,.*(\"\"#\"\"\")%\"xG\"\"$ F(%\"zGF(F(*(F'F()F*F'F()%\"yGF'F(!\"\"*&F*F(F,F(F(*$F/F(F1*&F+F(F)F(F (*&F+F()F,F'F(F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "By constructi on, the polynomial f is in the ideal . " }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 15 "with(Groebner);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#78%*MulMatrixG%)SetBasisG%0ToricIdealBasisG%*fglm_algoG%'gbasisG %'gsolveG%+hilbertdimG%,hilbertpolyG%.hilbertseriesG%-inter_reduceG%*i s_finiteG%,is_solvableG%*leadcoeffG%(leadmonG%)leadtermG%(normalfG%/pr etend_gbasisG%'reduceG%&spolyG%*termorderG%*testorderG%)univpolyG" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "leadterm(f,tdeg(x,y,z)); lea dterm(f,plex(x,y,z)); leadterm(f,plex(z,y,x));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&)%\"xG\"\"#\"\"\")%\"yGF&F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&)%\"xG\"\"$\"\"\"%\"zGF'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*$)%\"zG\"\"#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "leadcoeff(f,tdeg(x,y,z));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#!\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "lead mon(f,plex(x,y,z));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"#*&)%\"xG\" \"$\"\"\"%\"zGF(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "f1; f2; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*&%\"xG\"\"\"%\"zGF&F&*$)%\"yG\" \"#F&!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*$)%\"xG\"\"$\"\"\"F(* $)%\"zG\"\"#F(!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "spol y( f1, f2, plex(x,y,z) );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*&)%\"x G\"\"#\"\"\")%\"yGF'F(!\"\"*$)%\"zG\"\"$F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "S12 := expand( x^2*f1-z*f2 );" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%$S12G,&*&)%\"xG\"\"#\"\"\")%\"yGF)F*!\"\"*$)%\"zG\" \"$F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "normalf( S12, [f 1,f2], plex(x,y,z) );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*&)%\"xG\" \"#\"\"\")%\"yGF'F(!\"\"*$)%\"zG\"\"$F(F(" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 34 "G1 := gbasis([f1,f2],plex(x,y,z));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#G1G7',&*$)%\"yG\"\"'\"\"\"F+*$)%\"zG\"\"&F+!\" \",&*&%\"xGF+F.F+F+*$)F)\"\"#F+F0,&*&F3F+)F)\"\"%F+F+*$)F.F:F+F0,&*&)F 3F6F+F5F+F+*$)F.\"\"$F+F0,&*$)F3FBF+F+*$)F.F6F+F0" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 34 "G2 := gbasis([f1,f2],tdeg(x,y,z));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#G2G7$,&*&%\"xG\"\"\"%\"zGF)!\"\"*$)%\"yG \"\"#F)F),&*$)F(\"\"$F)F)*$)F*F/F)F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "Verify that f is in the ideal " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "normalf(f,G1,plex(x,y,z));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "nor malf(f,G2,tdeg(x,y,z));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "The graph k-coloring examples. Th is is the graph for the cycle on n=5 vertices V" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 64 "n := 3; V := [1,2,3,4,5]; E := \{\{1,2\},\{2,3 \},\{3,4\},\{4,5\},\{5,1\}\}; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" nG\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"VG7'\"\"\"\"\"#\"\"$\" \"%\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"EG<'<$\"\"#\"\"$<$\"\" \"F'<$F(\"\"%<$F,\"\"&<$F*F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "k := 2; # try two colors" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" kG\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "S := \{seq( x[v] ^k+1, v=V )\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG<',&*$)&%\"xG6 #\"\"\"\"\"#F,F,F,F,,&*$)&F*6#F-F-F,F,F,F,,&*$)&F*6#\"\"$F-F,F,F,F,,&* $)&F*6#\"\"%F-F,F,F,F,,&*$)&F*6#\"\"&F-F,F,F,F," }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 88 "Eeqns := proc(e) local u,v;\n u,v := op(e); \+ normal( (x[u]^k-x[v]^k)/(x[u]-x[v]) ) \nend;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&EeqnsGj+6#%\"eG6$%\"uG%\"vG6\"F+C$>6$8$8%-%#opG6#9$- %'normalG6#*&,&)&%\"xG6#F/%\"kG\"\"\")&F<6#F0F>!\"\"F?,&F;F?FAFCFCF+F+ F+6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Eeqns(E[1]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&&%\"xG6#\"\"#\"\"\"&F%6#\"\"$F(" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "S := S union \{seq( Eeqns( e), e=E )\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"SG<,,&*$)&%\"xG6# \"\"\"\"\"#F,F,F,F,,&*$)&F*6#F-F-F,F,F,F,,&*$)&F*6#\"\"$F-F,F,F,F,,&*$ )&F*6#\"\"%F-F,F,F,F,,&*$)&F*6#\"\"&F-F,F,F,F,,&F1F,F6F,,&F)F,F1F,,&F6 F,F " 0 "" {MPLTEXT 1 0 22 "X := seq( x[v], v=V );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"XG6' &%\"xG6#\"\"\"&F'6#\"\"#&F'6#\"\"$&F'6#\"\"%&F'6#\"\"&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "gbasis( S, plex(X) );" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "Thus the graph G is not 2-colorable" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "k := 3;\nS := \{seq( x[v]^k+1, v=V )\} union \{seq( E eqns(e), e=E )\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"kG\"\"$" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"SG<,,(*$)&%\"xG6#\"\"#F,\"\"\"F-*& &F*6#\"\"$F-F)F-F-*$)F/F,F-F-,(*$)&F*6#\"\"%F,F-F-*&F7F-&F*6#\"\"&F-F- *$)F;F,F-F-,(*$)&F*6#F-F,F-F-*&FCF-F)F-F-F'F-,(FAF-*&F;F-FCF-F-F>F-,(F 2F-*&F7F-F/F-F-F5F-,&*$)FCF1F-F-F-F-,&*$)F)F1F-F-F-F-,&*$)F/F1F-F-F-F- ,&*$)F7F1F-F-F-F-,&*$)F;F1F-F-F-F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "gbasis( S, plex(X) );" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7),&*$)&%\"xG6#\"\"&\"\"$\"\"\"F,F,F,,(*$)&F(6#\"\"%\"\"#F,F,*&F 0F,F'F,F,*$)F'F3F,F,,**$)&F(6#F+F3F,F,*&F0F,F:F,F,F4!\"\"F5F=,,*$)&F(6 #F3F3F,F,*&F:F,FAF,F,F " 0 "" {MPLTEXT 1 0 113 "n := 8;\nV \+ := [$1..8];\nE := \{\{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\}\};" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"VG7*\"\"\"\"\"#\"\"$\"\"%\"\"&\"\"'\"\"(\"\")" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"EG<0<$\"\"%\"\"(<$\"\"#\"\"$<$\"\" \"F*<$F+F'<$F'\"\"&<$F-F0<$F-\"\"'<$F*F'<$F*\"\")<$F+F6<$F0F(<$F3F(<$F (F6<$F0F3" }}}{EXCHG }{EXCHG }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m := nops(E);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"#9" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "X := seq( x[v], v=V );" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"XG6*&%\"xG6#\"\"\"&F'6#\"\"#&F'6# \"\"$&F'6#\"\"%&F'6#\"\"&&F'6#\"\"'&F'6#\"\"(&F'6#\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "k := 3; S := \{seq( x[v]^k+1, v=V ) \} union \{seq( Eeqns(e), e=E )\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%\"kG\"\"$" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"SG<8,(*$)&%\"xG6#\" \"#F,\"\"\"F-*&&F*6#\"\"$F-F)F-F-*$)F/F,F-F-,(*$)&F*6#\"\"%F,F-F-*&F7F -&F*6#\"\"&F-F-*$)F;F,F-F-,&*$)&F*6#\"\"'F1F-F-F-F-,&*$)&F*6#\"\"(F1F- F-F-F-,&*$)&F*6#\"\")F1F-F-F-F-,(*$)&F*6#F-F,F-F-*&FUF-F)F-F-F'F-,(FSF -*&F;F-FUF-F-F>F-,(F2F-*&F7F-F/F-F-F5F-,&*$)FUF1F-F-F-F-,&*$)F)F1F-F-F -F-,&*$)F/F1F-F-F-F-,&*$)F7F1F-F-F-F-,&*$)F;F1F-F-F-F-,(*$)FIF,F-F-*&F 7F-FIF-F-F5F-,(F'F-*&F7F-F)F-F-F5F-,(*$)FCF,F-F-*&FUF-FCF-F-FSF-,(*$)F OF,F-F-*&F/F-FOF-F-F2F-,(F`pF-*&F)F-FOF-F-F'F-,(F\\pF-*&FIF-FCF-F-FfoF -,(FfoF-*&F;F-FIF-F-F>F-,(FfoF-*&FOF-FIF-F-F`pF-,(F\\pF-*&F;F-FCF-F-F> F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "G := gbasis(S,tdeg(X) );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG7*,&&%\"xG6#\"\"'\"\"\"&F( 6#\"\")!\"\",(&F(6#\"\"&F+F,F+&F(6#\"\"(F+,&&F(6#\"\"%F+F,F/,&&F(6#\" \"$F+F4F/,(&F(6#\"\"#F+F4F+F,F+,&&F(6#F+F+F4F/,(*$)F4FBF+F+*&F,F+F4F+F +*$)F,FBF+F+,&*$)F,F>F+F+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "_EnvExplicit := true;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%-_Env ExplicitG%%trueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 80 "The six solut ions tell us that there are six color assignments for the vertices." } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "sols := solve( \{op(G)\}, \+ \{X\} );" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%solsG6(<*/&%\"xG6#\"\"% !\"\"/&F)6#\"\"'F,/&F)6#\"\")F,/&F)6#\"\"#,&#\"\"\"F8F;*&^##F,F8F;\"\" $F:F;/&F)6#\"\"&F9/&F)6#F?,&F:F;*&^#F:F;F?F:F;/&F)6#F;FG/&F)6#\"\"(FG< *F'F-F1/F6FG/FAFG/FEF9/FKF9/FNF9<*/FKF,/F.FG/F(FG/F2FG/FEF,/FNF,F5F@<* FX/F.F9/F(F9/F2F9FfnFgnFRFS<*FYFZFen/F6F,/FAF,FTFUFV<*FinFjnF[oF]oF^oF DFJFM" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "The colors are the roots of unity, i.e., -1, 1/2+-" }{XPPEDIT 18 0 "i*sqrt(3);" "6#*&%\"iG\"\" \"-%%sqrtG6#\"\"$F%" }{TEXT -1 4 " /2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "subs( \{1/2+sqrt(3)*I/2=red, 1/2-sqrt(3)*I/2=blue, -1 =green\}, [sols] );" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7(<*/&%\"xG6#\" \"%%&greenG/&F'6#\"\"'F*/&F'6#\"\")F*/&F'6#\"\"#%%blueG/&F'6#\"\"$%$re dG/&F'6#\"\"\"FF7 /FBF7<*F3/F>F*/F,F " 0 " " {MPLTEXT 1 0 0 "" }}}}{MARK "37 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }