The Grobner Annihilator Graph of a Ring

PAGE 1

TheGrobnerAnnihilatorGraphofaRing By TrevorMcGuire AThesis SubmittedtotheDivisionofNaturalSciences NewCollegeofFlorida inpartialfulllmentoftherequirementsforthedegree BachelorofArts UnderthesponsorshipofDr.EiriniPoimenidou Sarasota,FL May,2009

PAGE 2

TheGrobnerAnnihilatorGraphofaRing ByTrevorMcGuire NewCollegeofFlorida,2009 ABSTRACT Inrecentyears,graphtheoryhasbeenusedasatooltostudyringsintheformof severaldierentgraphs,manyofwhicharebasedonthezerodivisorstructureofthe ring.Wedeneheretheannihilatorgraphofaringtotrytoharnessthebestpossible graphicalrepresentationofaring.Thispaperlaysthefoundationforthetheoryof annihilatorgraphsandtheextensionofthemtoamoregeneralform,theGrobner annihilatorgraph.Wewillstudytherelationshipsbetweenthealgebraicproperties ofaring,andthegraphtheoreticpropertiesoftheGrobnerannihilatorgraphofthat ring. Dr.EiriniPoimenidou DivisionofNaturalSciences

PAGE 3

Contents 1.CommonSymbols1 2.Introduction2 3.PreliminaryDenitions2 3.1.Algebra3 3.2.GraphTheory6 4.ZeroDivisorGraph9 5.AnnihilatorGraph11 6.MonomialAnnihilatorGraph26 7.GrobnerBases39 8.GrobnerAnnihilatorGraph46 9.FurtherResearch56 References60

PAGE 4

1 1. CommonSymbols R Acommutativeringwithidentity k Aninniteeldwithcharacteristic0 I;J Monomialideals h I;J i Idealgeneratedbytheunionofthe generatorsof I and J I g IdealwithaGrobnerbasis ^ I TheArtinianclosureof I LT I Leadingtermidealof I ~ I LT I \050 R Zerodivisorgraphof R )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R Annihilatorgraphof R )]TJ/F34 7.9701 Tf 7.315 -1.793 Td [(m R Monomialannihilatorgraphof R )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(g R Grobnerannihilatorgraphof R A Thesetofantichainsof A P A Powersetof A G Thecliquenumberofagraph G K n Completegraphon n vertices H GH isasubgraphof G Multivariatemonomialormorevariables PMGPairedmonomialgenerator,Denition8 : 5 H n Denitiononpage48 X X 1 ;:::;X n h X ih X 1 1 ;:::;X n n i ; = 1 ;:::; n X Q n i =1 X i i ; = 1 ;:::; n Z n 0 n )]TJ/F15 11.9552 Tf 11.955 0 Td [(tuplesofnonnegativeintegers RelationdenedinProposition5 : 2 Z R Zerodivisorsofaring R E Graphwithnoedges

PAGE 5

2 2. Introduction Thenotionofthezerodivisorgraphofaringwasrstintroducedin1988byBeckto studygraphcolorings[4].Manyhaveelaboratedonthesegraphsandfoundrelations betweenthegraphsandtherings.Here,wewishtoworkwithamoregeneralgraph whichhasevolvedfromthezerodivisorgraph,andwhoseoriginalformulationisdue toMulay[14].Insteadofindividualzerodivisorsaswerepreviouslyused,Mulayused equivalenceclassesofzerodivisorsandhadonerepresentativeforeachequivalence class.Thishadmanyadvantagesoverthezerodivisorgraph,themostnotableone beingthatofnitenessofthegrapheveninthecaseofinniterings. Inthefollowingsections,wewillmodifyMulay'sequivalenceclassgraphinan attempttondabettergraphicalrepresentationofaringwhilepossiblyeradicatingsomeoftheshortcomingsofthesegraphs.Onesuchshortcomingisthelackof uniquenessofthegraphs. Insection5,wewillintroducetheannihilatorgraphofaringandshowthatit uniquelydeterminesapolynomialring k [ X 1 ;:::;X n ] =I where I isacertaintype ofmonomialidealand k isaninniteeldwithcharacteristic0.Insections6,7, and8,wewilluseasubgraphoftheannihilatorgraphcoupledwithGrobnerbases todenetheGrobnerannihilatorgraph,whichgeneralizestheannihilatorgraphto allpolynomialringsover k .Therestofourdiscussionwillconcerntherelationships betweentheGrobnerannihilatorgraphandtheringitcamefrom,andfutureresearch directions. Theresearchforsection5wasconductedprimarilyduringtheMissouriStateUniversityResearchExperienceforUndergraduatesinthesummerof2008underDrs. CameronWickhamandLesReid. 3. PreliminaryDefinitions Inthissection,wewillsimplystateseveraldenitionsandexamplesthatthereader needstobefamiliarwithbeforewecanbeginourstudyofannihilatorgraphs.

PAGE 6

3 3.1. Algebra. Denition3.1. Aring R isasetwithtwobinaryoperations,+and ,usuallycalled additionandmultiplication,respectively,withthefollowingproperties: R; +isanadditiveabeliangroup. R isclosedunderanassociativemultiplication. Forall a;b;c 2 R a b + c = a b + a c .Similarlyforrightmultiplication. Wewillconcernourselvesprimarilywithringsthathaveoneadditional property: Forall a;b 2 R a b = b a .Theseringsaresaidtobecommutative. Furthermore,ifthereexistsanelement e 2 R suchthat e r = r e = r forall r 2 R then R issaidtobearingwithidentity,oraringwith1.Wewillusuallydenote e by1.Unlessotherwisestated, R willbeacommutativeringwith1. Example3.1. Theintegers Z formaringundertheusualoperationsofadditionand multiplication. Example3.2. Thepowerset P A ofaset A ,formsacommutativeringwith identityunderthesymmetricdierenceofsetsasaddition,andsetintersectionas multiplication.Thatis,fortwosets B;C B + C = B=C [ C=B ,and B C = B C Thisringhasanidentity,namely A ,sinceforall B A;A B = B A = B .Itis easytoseethattheadditiveidentityforthisringistheemptyset. Denition3.2. Inaring R withidentity,anelement u 2 R issaidtobeaunitif ux =1forsome x 2 R Example3.3. In Z ,thesetofunitsis f)]TJ/F15 11.9552 Tf 15.276 0 Td [(1 ; 1 g Denition3.3. Anonzeroelement z ofaring R issaidtobeazerodivisorif zx =0 forsomenonzero x 2 R .Wedenotethezerodivisorsof R by Z R .

PAGE 7

4 Example3.4. Considerthepowersetof Z 3 = f 0 ; 1 ; 2 g .Let R = P Z 3 withthe operationsfromExample3.2,making R aring.Notethat f 1 gf 2 g = f 1 gf 2 g = ; thus, f 1 g ; f 2 g2 Z R Denition3.4. If R isacommutativeringwith1andnozerodivisors,then R is saidtobeanintegraldomain. Example3.5. Weuse Z againhere,sinceforall z 1 ;z 2 2 Z ;z 1 z 2 =0implies z 1 =0 or z 2 =0.Thus,therearenozerodivisorsin Z .Theidentityelementis1. Denition3.5. Aeld k isacommutativeringwith1inwhicheverynonzeroelement isaunit.Itiseasytoseethatif k isaeld,then k isanintegraldomain,forif ab =0 for a;b 2 k ,and a 6 =0,then 1 a ab = b =0,therefore, b =0.I.e. k hasnozerodivisors. Example3.6. Therationals Q areaeldundertheusualoperationsofadditionand multiplication.Theintegersmoduloaprime p Z p alsoformaeld. Denition3.6. Wesayapolynomialringin n variablesoveraeld k ,denoted k [ X 1 ;:::;X n ]isthesetof n -variatepolynomialsdrawingcoecientsfrom k .Itisnot requiredthat k beaeld,butwewillbeconsideringonlythiscaseinourdiscussion.If thepolynomial f 2 k [ X 1 ;:::;X n ]hasonlyoneterm,thenitissaidtobeamonomial. Example3.7. Ifwetake Q [ X;Y ],wehaveacommutativeringwith1,withelements suchas5 X 2 )]TJ/F31 7.9701 Tf 13.151 4.708 Td [(3 2 Y 2 +2 XY )]TJ/F31 7.9701 Tf 13.15 4.708 Td [(5 3 Denition3.7. Inacommutativering R I R issaidtobeanidealifitsatises: I 6 = ; If f;g 2 I ,then f )]TJ/F33 11.9552 Tf 11.956 0 Td [(g 2 I If f 2 I;h 2 R ,then hf 2 I Denition3.8. WesayanidealIgeneratedbytheelements g 1 ;:::;g n 2 R ,written as h g 1 ;:::;g n i istheset f P n i =1 r i g i j r i 2 R g .Ifeach g i isamonomialin R ,then I is saidtobeamonomialideal.

PAGE 8

5 Therearemanytypesofideals,butonlythreewemustbefamiliarwith.Therst isthemonomialidealwhichwealreadydened,theothertwoaretheprimeideal, andtheprincipalideal. Denition3.9. Anideal I ofaring R issaidtobeaprimeidealif ab 2 I implies a 2 I or b 2 I Denition3.10. Anideal I ofaring R issaidtobeaprincipalidealif I = h g i for some g 2 I .Thatis,allprincipalidealscanbegeneratedbyasingleelement. Example3.8. Inthering Z ,itisclearthatthesetofevennumbersisanideal.I.e. 0iseven,thedierenceoftwoevenintegersiseven,andanevenintegermultiplied byanyotherintegerisalsoeven.Wecanwritethisidealingeneratorformas h 2 i = f 2 z j z 2 Z g .Wealsoseethat h 2 i isprimebecauseanyevennumbercan bewrittenas2 m forsome m ,and2 2h 2 i .Also,since h 2 i isgeneratedbyasingle element,itisprincipal. Itwillproveusefullatertobeabletoaddnewgeneratorstoexistingideals,and oftentomakeanewidealoutoftheunionofthegeneratorsoftwoideals.Fornotation purposes,ifwehavetwoideals, I and J ,wewilllet h I;J i betheidealgeneratedby theunionofthegeneratorsof I and J .Additionally, h I; 1 ;:::; n i willrepresent theidealgeneratedbyallthegeneratorsof I andeachofthe i Denition3.11. Amonomialtermorderingon k [ X 1 ;:::;X n ]isanyrelation > on Z n 0 ,orequivalently,anyrelationonthesetofmonomials X 2 Z n 0 satisfying: > isatotal,orlinearorderingon Z n 0 If > and 2 Z n 0 ,then + > + > isawellorderingon Z n 0 .Thismeansthateverynonemptysubsetof Z n 0 hasasmallestelementunder > Example3.9. Let = 1 ;:::; n ; = 1 ;:::; n 2 Z n 0 .Thelexicographicterm orderisdenedasfollows: > ifinthevectordierence )]TJ/F33 11.9552 Tf 11.858 0 Td [( 2 Z n ,theleftmost

PAGE 9

6 nonzeroentryispositive.Thisorderingclearlysatisestherst2criteriaforaterm order.Toseepart3,assumeitisnottrue.Let A Z n 0 andlet A = f 1 ;:::; n ;::: g Sincethereexistsnominimumelement,thenwithoutlossofgenerality,wehavethe followingdescendingsequenceofelements 1 > 2 > > n > Considertherstentriesofthevectors i 2 Z n 0 .Bythedenitionoflexicographic ordering,theserstentriesformanonincreasingsequenceofnonnegativeintegers. Since Z iswellordered,therstentriesofthe i smuststabilizeeventually. Thesecondentrycanbetreatedthesameway,andsimilarlyforalltheentries. Thus,thereexistsa j suchthat k = j forall k j .Thiscontradictstheinnite decreasingsequence,thereforetheredoesexistaleastelementasrequired. Example3.10. Let f 2 Q [ X;Y;Z ]suchthat f = 1 2 X 3 YZ 2 +5 X 7 Z 3 )]TJ/F15 11.9552 Tf 12.187 0 Td [(3 Y 8 .Then multideg f = ; 0 ; 3since5 X 7 Z 3 isclearlymaximalwithrespecttothelexicographictermorderwith X>Y>Z Denition3.12. Thecharacteristicofaeldisthesmallestpositiveinteger r such that r 1=0.Ifnosuch r exists,thecharacteristicissaidtobe0. Example3.11. Thecharacteristicof Z p is p .Thecharacteristicof C is0. 3.2. GraphTheory. Denition3.13. Agraph G consistsofanitenonemptyset V ofobjectscalled vertices,andaset E of2-elementsubsetsof V callededges.Thesets V and E are thevertexsetandedgesetrespectively,oftendenotedby V G and E G forclarity. Thesizeofagraph,denoted j G j willmeanthenumberofverticesinthegraph.I.e. j G j = j V G j .

PAGE 10

7 Foragraph G ,if f v;w g2 E G ,wewilloftenwrite vw todenotetheedgebetween vertices v and w .If f v;v g62 E G forall v 2 V G ,andeach f v;w g occursatmost oncein E G ,then G issaidtobeasimplegraph. Example3.12. Thefollowingisasimplegraphon7vertices. Denition3.14. Thedegreeofavertexisthenumberofedgesincidentwiththat vertex. Example3.13. InExample3.12,thedegreeof v 1 is4,writtendeg v 1 =4.Also, deg v 5 =1anddeg v 4 =0. Denition3.15. Thedegreesequenceofasimplegraphisamonotonicallyincreasing sequenceofthedegreesoftheverticesofthegraph. Example3.14. ThedegreesequenceofExample3.12is0,1,2,2,3,4,4. Denition3.16. Agraph G on n verticessuchthatforanytwovertices v 1 ;v 2 2 V G v 1 v 2 2 E G issaidtobeacompletegraphon n vertices,denoted K n Denition3.17. Agraph G issaidtobeacompletebipartitegraphif V G canbe partitionedinto2sets V 1 ;V 2 suchthatforall v 1 2 V 1 v 2 2 V 2 v 1 v 2 2 E G ,andfor all v i ;v j 2 V 1 v i v j 62 E G .Similarlyfor V 2 .

PAGE 11

8 Denition3.18. Agraph G with V G = f v 1 ;:::;v n g and E G = f v 1 v 2 ;v 2 v 3 ;:::;v n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 v n g issaidtobeapathoflength n )]TJ/F15 11.9552 Tf 11.955 0 Td [(1. Denition3.19. Agraphisconnectedifthereexistsapathbetweeneverypairof vertices.Amaximalconnectedsubgraphofagraphiscalledacomponent,andifa graphisnotconnected,itcontainsatleasttwocomponents. Denition3.20. Agraph G with V G = f v 1 ;:::;v n g and E G = f v 1 v 2 ;v 2 v 3 ;:::;v n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 v n ;v n v 1 g issaidtobeacycleoflength n Example3.15. InExample3.12,thesubgraphinducedonthevertices v 2 ;v 3 ;v 6 ; and v 7 isapathoflength3.Thesubgraphinducedon v 1 ;v 2 ; and v 7 isacycleofsize3. Denition3.21. AHamiltonianpathofagraph G isasubgraphthatisapathsuch thateachvertexofthegraphisvisitedbythepathexactlyonce.AHamiltonian cycleisasubgraphthatisacyclewiththesameproperty. Denition3.22. Atreeisaconnectedsimplegraphwithnocycles. Example3.16. WeremoveafewedgesfromExample3.12tocreatethefollowing tree: Denition3.23. Theemptygraphisagraph G suchthat j G j6 =0and E G = ; .

PAGE 12

9 4. ZeroDivisorGraph Inthissection,wewillgiveanoverviewofthezerodivisorgraphofaring,afew examples,andsomeproperties.Thisshouldgivethereaderaavorofwhatthisarea ofresearchinalgebraconsistsof.Theresultsstatedhereareforreferencepurposes later,asmanyoftheresultswillhaveanalogueswithannihilatorgraphsinlater sections.Proofsaregivenwhentheyarehelpfulinlaterproofs.Mostofthissection canbefoundin[2]. Consideraring R anditssetofzerodivisors Z R .Associateasimplegraph,\050 R with R thathasvertexset Z R .Elements x;y 2 Z R willbeadjacentin\050 R if andonlyif xy =0 2 R .Consequently,\050 R istheemptygraphifandonlyif R is anintegraldomain. Example4.1. Let R = P f 1 ; 2 ; 3 g undertheoperationsofExample3.2.Then Z R = ff 1 g ; f 2 g ; f 3 g ; f 1 ; 2 g ; f 1 ; 3 g ; f 2 ; 3 gg and\050 R is Example4.2. Let F 4 betheniteeldof4elements.Wemaythinkof F 4 as Z 2 where = x + h x 2 + x +1 i isarootof x 2 + x +1in Z 2 [ x ] = h x 2 + x +1 i : Inthislight,wehave F = f 0 ; 1 ;; +1 g .Withthis,wehavethat R = Z 2 F 4 = f ; 0 ; ; 1 ; ; ; ; 1+ ; ; 0 ; ; 1 ; ; ; ; 1+ g ,and Z R = f ; 1 ; ; ; ; 1+ ; ; 0 g .Then thezerodivisorgraph\050 R is

PAGE 13

10 Theorem4.1. Theorem2.2[2] Let R beacommutativeringandlet \050 R beits zerodivisorgraph.Then \050 R isniteifandonlyifeither R isnite,oranintegral domain.Inparticular,if 1 j \050 R j < 1 ,then R isnite,andnotaeld. Proof. Clearly,if R isnite,oranintegraldomain,\050 R isnite,orempty,respectively.Assume\050 R isniteandnonempty,thenthereexistsnonzero x;y 2 R such that xy =0.Let A = f r 2 R j rx =0 g ,then A isnite,nonempty,andasubset of Z R byconstruction.Also, sy 2 A forall s 2 R since xsy = sxy = s =0. Therefore,wehaveelementsof A whicharemultiplesof y ringelementmultiples. Let a 2 A besuchanelement,andconsider B a = f r 2 R j ry = a g .Notice B a is nonemptybyconstruction.If R isinnite,and A isnite,thenwemusthavesome a 2 A suchthattheset B a isinnite.I.e.,thereexistsan a 2 A suchthat ry = a foraninnitenumberof r 2 R .Thus,forall b 1 ;b 2 2 B a ,wehave b 1 y = b 2 y = a andhence, b 1 )]TJ/F33 11.9552 Tf 12.62 0 Td [(b 2 y =0.Therefore, b 1 )]TJ/F33 11.9552 Tf 12.62 0 Td [(b 2 2 Z R .Since B a isinnite,this causes Z R tobeinnite,whichisacontradictionsince\050 R isnite.Therefore, R isnite. Theorem4.2. Theorem2.3[2] Let R beacommutativering,then \050 R isconnected. Proof. Let x;y 2 Z R bedistinct.If xy =0,thentheyareconnected,soassume xy 6 =0.If x 2 = y 2 =0,thenwehavethepath x;xy;y ,andthus x and y areconnected. Soweassumethat x 2 =0and y 2 6 =0.Thentheremustbea b 2 Z R )-216(f x;y g such that by =0.If bx =0,wehavethepath x;b;y .If bx 6 =0,wehavethepath x;bx;y Theargumentissimilarif y 2 =0and x 2 6 =0,sowemayassumethat xy;x 2 ; and

PAGE 14

11 y 2 areallnonzero.Hence,thereare a;b 2 Z R )-244(f x;y g suchthat ax = by =0.If a = b ,thepathis x;a;y ,sowemayassume a 6 = b .If ab =0,thepathis x;a;b;y ,and if ab 6 =0,wehave x;ab;y .Thus,wehavedemonstratedapathbetween x;y 2 Z R forallpossiblecases. Theorem4.3. Theorem2.5[2] Let R beacommutativering,and \050 R itszero divisorgraph.Thenthereisavertexof \050 R thatisadjacenttoeveryothervertex ifandonlyifeither R = Z 2 A where A isanintegraldomain,or Z R [f 0 g isa primeidealof R Theorem4.4. Theorem2.8[2] Let R beacommutativering,and \050 R itszero divisorgraph.Then \050 R isacompletegraphifandonlyifeither R = Z 2 Z 2 or xy =0 forall x;y 2 Z R Theproofsoftheprecedingtheoremshavebeenomittedbecausethetechniques usedinthemwillnotbeusefultousinlatertheorems.Theinterestedreadercan referto[2]forthecompleteproofs. 5. AnnihilatorGraph Let k beaninniteeldwithcharacteristic0,andlet I beamonomialidealin thering k [ X 1 ;:::;X n ].Weconsiderthering R = k [ X 1 ;:::;X n ] =I anduselowercase letterstodenotethecosets,thatis,set x i = X i + I for1 i n .Inmanyofthefollowingtheorems,theresultsremaintrueforanyringoveraninniteintegraldomain, buttherequirementthat k beaeldarisesfromtheneedtousethedivisionalgorithm inlatertheorems,soweopttousetheeldthroughout.Furthermore,fornotation purposes,weshallabbreviate k [ X 1 ;:::;X n ]as k [ X ]where X willbeunderstoodto be n variables.Thelongernotationwillbeusedoccasionallywhentheabbreviated notationcouldcauseconfusion.Let M I = f 2 Z R j = Q n i =1 x i i ; 0 i 2 Z g

PAGE 15

12 bethesetofzerodivisormonomialsin R .Wedeneapartialorder, on M I by n Y i =1 x i i n Y i =1 x i i ifandonlyif i i forall i Consider n =2andnoticethat x a y b x a y b since a a and b b If x a y b x c y d and x c y d x a y b ,then a c;c a;b d ,and d b ,thus a = c and b = d .Finally,if x a y b x c y d x e y f ,thenwesee a c e and b d f ,thus, x a y b x e y f .Since thisclearlygeneralizestoanarbitrary n ,weseethat satisestherequirementsof apartialorderingon M I Itwillprovehelpfultothinkofmonomialswiththefollowingnotation.Let = 1 ;:::; n 2 Z n 0 anddenotethemonomial x 1 1 x n n by x .Withthisnotation, x x ifandonlyif )]TJ/F33 11.9552 Tf 11.956 0 Td [( 2 Z n 0 Example5.1. Let R = k [ X;Y ] = h X 3 ;Y 2 i .Thenwehave M I = f x;x 2 ;y;xy;x 2 y g where x x 2 y and x 2 6 xy .Noticethatsince isapartialorder, x 2 6 xy doesnot imply xy x 2 Denition5.1. Let A;B M I .Themonomialsetproductof A and B istheset givenby AB = f ab j a 2 A;b 2 B g Wewilloftenusethewordproductforthemonomialsetproductforsimplicity,if itisclearfromthecontextwhatismeant.If AB = f 0 g ,wewillsay AB =0 Remark 5.1 Noticethatthecommutativityandassociativityoftheringholdsfor thisproduct. Example5.2. Consider R = k [ X;Y ] = h X 3 ;Y 4 i .Let A = f x 2 y;xy 3 g ;B = f y 2 ;xy;x 2 g and C = f x 2 y 3 g .Then AB = f 0 ;x 2 y 3 g and AC =0. Denition5.2. Let A M I .Themonomialsetannihilatorof A istheset Ann A = f B M I j AB =0 g

PAGE 16

13 Wewilloftenusethewordannihilatorformonomialsetannihilatorforsimplicity, ifitisclearfromthecontextwhatismeant.Furthermore,Ann f a g ,theannihilator ofthesetcontainingjustoneelementwillbewrittenasAnn a Example5.3. With R;A;B;C asinExample5.2, C 2 Ann A ,and B 62 Ann A Example5.4. Let R = k [ X;Y ] = h X 3 ;Y 2 i ,thenAnn x 2 y = P M I andAnn xy = P f x 2 ;x 2 y;y g .Noticethat x 2 y = xy x andAnn xy Ann x 2 y Let A and A 0 besubsetsof M I suchthat A 0 A .If 2M I and a =0forall a 2 A ,thenclearly a 0 =0forall a 0 2 A 0 .ItfollowsthatAnn A Ann A 0 Lemma5.1. Let A M I ,andsuppose ; 2 A suchthat ,then Ann A = Ann A )-222(f g Proof. Let A 0 = A )-326(f g .WehavebytheprecedingcommentthatAnn A Ann A 0 .Since ,thenwehavethat = forsome 2M I .Thus,if isa monomialsuchthat =0,then =0.Itfollowsthatforany B M I ,if BA 0 =0, then BA =0;thatis,Ann A 0 Ann A andthus,Ann A =Ann A 0 Denition5.3. Let R = k [ X ] =I andlet ; 2M I ,then and arecalledcomparableif or .If 6 and 6 ,thentheyarecalledincomparable. If A M I ,andforall ; 2 A and areincomparable,then A iscalledan antichain.Ifallelementsofasetarecomparable,thesetiscalledachain.Fora set A ,let A bethesetofantichainsof A .Singlemonomialstriviallysatisfythe denitionofanantichain. Example5.5. Consider R = k [ X;Y ] = h X 3 ;Y 5 i .Then A = f x 2 y;xy 3 g and B = f y 2 ;xy;x 2 g arebothantichains.However,theset AB = f 0 ;x 2 y 3 ;x 2 y 4 g isnotan antichainbecause x 2 y 3 x 2 y 4 Proposition5.1. If ; 2 Z n 0 ,and ifandonlyif )]TJ/F33 11.9552 Tf 12.096 0 Td [( 2 Z n 0 ,thenunder thispartialordering,allantichainsof Z n 0 arenite.

PAGE 17

14 Noticethatthisisthesamepartialorderingdenedaboveformonomials,but denedhereon Z n 0 Proof. Noticethat 6 ifandonlyifthereexistssome i;j suchthat i > i 0 and j > j 0.If n =1,thensinceantichainsof Z 0 aresingletons,theresultis truefor n =1.Assumetheresultholdsforallintegerslessthan n .Let A Z n 0 andlet = 1 ;:::; n 2 A .Assume A isaninniteantichain.Theneveryother elementof A musthaveatleastonecomponentwhichislessthanthecorresponding componentof .Sincethereareaninnitenumberofelements,andonlyanite numberofcomponentsin ,itfollowsthatthereexistsatleastonecomponentfor whichaninnitenumberofelementsin A haveavalueinthatcomponentlessthan thatof .Withoutlossofgenerality,let 1 satisfythiscondition.Thenwehave aninnitenumberof n -tuplessuchthattherstcomponentislessthan 1 .Since thereareonlyanitenumberofchoicesforthatentry,thentheremustexistan innitenumberof n -tupleswhichareequalintherstcomponent.Callthesetof these n -tuples A 0 .Since A 0 A A 0 isstillanantichain.Wehave,though,thateach elementof A 0 hasthesamerstcomponent,therefore,whenitcomestocomparing them,wecanignorethatcomponent.Thismeansthatwehaveaninniteantichain in Z n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 0 ,whichcontradictsourinductivehypothesis.Thus,allantichainsof Z n 0 are nite. Corollary5.1. Let R = k [ X ] =I where I = h X i ; 2 Z n 0 ,thenallantichainsof M I arenite. Proof. Sinceeachelementof M I correspondstoasingleelementin Z n 0 ,itfollows thatanyantichainof M I willcorrespondtoanantichainof Z n 0 .Theseantichains areallnite,soanyantichainsof M I arealsonite. Lemma5.2. Let 2 Z n 0 andlet R = k [ X ] = h X i .Suppose ; 2M I ,then Ann Ann ifandonlyif .

PAGE 18

15 Proof. If ,then = forsomemonomial .Hence,if isamonomial,and =0in R ,then = =0in R .SoAnn Ann Conversely,supposeAnn Ann .Let = Q n i =1 x k i i ; = Q n i =0 x l i i where 0 k i ;l i < i .Thenforeach i x i )]TJ/F34 7.9701 Tf 6.586 0 Td [(k i i =0in R .So f x i )]TJ/F34 7.9701 Tf 6.586 0 Td [(k i i g2 Ann Ann Hence x i )]TJ/F34 7.9701 Tf 6.586 0 Td [(k i i =0in R .So x i )]TJ/F34 7.9701 Tf 6.587 0 Td [(k i i 2 I ,whichimpliesthat x i )]TJ/F34 7.9701 Tf 6.586 0 Td [(k i i = x i i forsome monomial 2 I .But x i )]TJ/F34 7.9701 Tf 6.587 0 Td [(k i i = x i )]TJ/F34 7.9701 Tf 6.586 0 Td [(k i + l i i Q j 6 = i x l j j =0.Hence, i )]TJ/F33 11.9552 Tf 12.045 0 Td [(k i + l i i ,and therefore, l i k i .Sincethisholdsforeach i ,then asrequired. Lemma5.3. Let R = k [ X ] =I where I isamonomialidealsuchthat M I isinnite, andlet A M I where A isinnite.Thenthereexistsanite B A suchthat Ann A =Ann B and B isanantichain. Proof. Let A M I .If A containsanychains,let C beonemaximalchain,andlet C = f 1 ;:::; n ;::: g where 1 2 n .Wesayachainismaximalin thesensethatitisnotcontainedinanyotherchains.Let A 1 = A )-130(f 2 ;:::; n ;::: g ThenbyrepeatedapplicationsofLemma5.1,Ann A =Ann A 1 .If A 1 contains anychains,werepeattheargument.Continuingthisway,theprocesswillterminate when A k isanantichain.Thisprocesswillterminatebyvirtueofthefactthatany innitechainisnecessarilyassociatedwithanunboundedvariableinthegenerating setof I .Sincewehaveonlyanitenumberofvariables,thenthenumberofmaximal innitechainsisnite.AgainbyLemma5 : 1,wehavethatAnn A =Ann A k where A k isanantichain.Let B = A k ,andwehavethedesiredresult. Proposition5.2. Let R = k [ X ] = h X i .Denearelation, on P M I by A B if andonlyif Ann A =Ann B .Thenwehave Therelation on P M I isanequivalencerelation. Eachequivalenceclassof isuniquelyrepresentedbyanantichainof M I Themonomialsetproductrespects ;thatis,if A A 0 and B B 0 ,then AB A 0 B 0 .Consequently,themonomialsetproductiswelldenedonthe setofequivalenceclassesin M I denedby .

PAGE 19

16 Proof. Clearly,Ann A =Ann A ,so A A .Similarly,Ann A =Ann B implies Ann B =Ann A .Transitivityfollowsimmediately,aswell. Let A k betheantichainsuchthatAnn A =Ann A k asoutlinedintheproof ofLemma5.3. Wenextneedtoshowthatoncewegetourantichain, A k ,ifwetakeout anothermonomial,say 1 ,thenAnn A k )-327(f 1 g 6 =Ann A k .Let 1 = Q n j =1 x k j j andfor i 2 A k i = Q n j =1 x l j j .Ifwelet = Q n j =1 x j )]TJ/F34 7.9701 Tf 6.586 0 Td [(k j )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 j thencertainly, 62 Ann A k since 1 6 =0.Itremainstoshowthat 2 Ann A k )-272(f 1 g .Todothis,wemustshowthatforeach i 2 A k )-272(f 1 g thereisonevariablewhichhasanexponentstrictlygreaterthanthesame variablein ,thusassuringthat i =0.Assumethisisfalse,thenforeach variable, x j in ,wehavethat i = Q n j =1 x j )]TJ/F34 7.9701 Tf 6.586 0 Td [(k j +1+ l j j .If i 6 =0,thenwe havethat j )]TJ/F33 11.9552 Tf 12.004 0 Td [(k j +1+ l j < j forall j .Thisimplies k j l j forall j ,which implies j .Thiscontradictsthefactthat A k isanantichain,andthe resultfollows. Suppose M 2 Ann AB ,then MAB =0andwehavethat MA 2 Ann B = Ann B 0 .Hence, MAB 0 =0and MB 0 2 Ann A =Ann A 0 .Thus, MA 0 B 0 = 0and M 2 Ann A 0 B 0 .Theconverseholdsbythesymmetricargument. Unlessotherwiseindicated,anyreferencetoequivalenceclasses,relation,or ,will allbewithrespecttotheequivalencerelationdenedabove. Denition5.4. Let k beaninniteeldofcharacteristic0,andlet R = k [ X ] =I where I issomemonomialideal.Theannihilatorgraphof R ,denoted)]TJ/F34 7.9701 Tf 62.764 -1.793 Td [(a R is thegraphwhoseverticesaretheequivalenceclasses[ A ]oftherelation dened on P M I ,andwhoseedgesaretheorderedpairs[ A ] ; [ B ]ofequivalenceclasses satisfying AB =0.

PAGE 20

17 Example5.6. Consider R = k [ X;Y ] = h X 2 ;Y 2 i .Then M I = f x;y;xy g .Since theverticesof)]TJ/F34 7.9701 Tf 86.632 -1.793 Td [(a R aretheequivalenceclassesdeterminedby ,andsinceeach equivalenceclassisuniquelyrepresentedbyanantichain,thenwemayidentifyeach antichainwithitsequivalenceclassvertexandthinkoftheverticesof)]TJ/F34 7.9701 Tf 373.522 -1.793 Td [(a R asthe antichainsof M I = f x;y;xy g .Hence,theverticesof)]TJ/F34 7.9701 Tf 125.436 -1.794 Td [(a R are f [ x ] ; [ y ] ; [ xy ] ; [ f x;y g ] g Then)]TJ/F34 7.9701 Tf 37.88 -1.793 Td [(a R isthegraph Itisinterestingtonotethatthisgraphisisomorphictothezerodivisorgraphof Z 2 F 4 asdenedin[2]. Example5.7. Consider R = k [ X;Y ] = h X 3 ;Y 2 i .Then M I = f x;x 2 ;y;xy;x 2 y g and V )]TJ/F34 7.9701 Tf 11.866 -1.793 Td [(a R = f [ x ] ; [ x 2 ] ; [ y ] ; [ xy ] ; [ x 2 y ] ; [ f x;y g ] ; [ f x 2 ;xy g ] ; [ f x 2 ;y g ] g and)]TJ/F34 7.9701 Tf 30.076 -1.793 Td [(a R is Lemma5.4. Suppose R = k [ X ] = h X 1 1 ;:::;X n n i ,with k i forall i ,thenthe vertexrepresentedbythemonomial k = x k )]TJ/F31 7.9701 Tf 6.586 0 Td [(2 k Q i 6 = k x i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i hasthesecondhighest degreein )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R .

PAGE 21

18 Proof. Considerthemonomial = Q n i =1 x i )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 i .Weseethat x i =0forall i ,and assuch,Ann = P M I .Thus,[ ]isclearlythevertexofmaximaldegreein )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R ,sincedeg[ ]= j )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R j)]TJ/F15 11.9552 Tf 19.971 0 Td [(1.SincewehavebyLemma5.2that k impliesAnn k Ann ,itfollowsimmediatelythatdeg[ k ] deg[ ].Since x k 2 Ann ,and x k 62 Ann k ,wehaveastrictinequality,deg[ k ] < deg[ ]. Tocompletetheproof,assumethereexistssomeantichain A 2 M I suchthat .1deg[ k ] < deg[ A ] < deg[ ] Suppose A containsexactlyonemonomial, j whichisnot or k .Itisclearthat ifwestartwith andreduceanyoftheexponentsonanyofthevariables,thenthe sizeoftheannihilatorassociatedwiththatnewmonomialwillbelessthanAnn Furthermore,ifonereducesonevariable'sexponentby2,creatingamonomialofthe form x l )]TJ/F31 7.9701 Tf 6.587 0 Td [(3 l Q i 6 = l x i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i ,thentheannihilatorofthiselementisstrictlysmallerthanthe annihilatorofthemonomial x l )]TJ/F31 7.9701 Tf 6.586 0 Td [(2 l Q i 6 = l x i )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 i .Becauseofthis,weseethatthelargest annihilatorsofsingleelementsmustbeoftheformofthelattermonomial.Thus,if A = f j g ,thentheonlyreasonablepossibilityfor j is j = x j )]TJ/F31 7.9701 Tf 6.586 0 Td [(2 j Q i 6 = j x i )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 i .By thehypotheses,though, k j ,therefore,deg[ k ] deg[ j ]whichcontradicts .1.Thisshowsusthatif A existsasper.1,thenitmustcontainmorethan1 element. Suppose A = f 1 ;:::; m g ,with m> 1 ; i 2M I ,thenAnn A = m i =1 Ann i therefore,Ann A Ann i forall i .Hencedeg[ A ]= j Ann A jj Ann i j = deg[ i ]forall i .Wehave,though,thatforthelargestpossible i j Ann i j j Ann k j .Thus,ifweassumethat j A j > 1,weonceagaincontradict.1. Therefore,nosuch A exists,asrequired. Lemma5.5. Suppose ; 2 Z n 0 suchthat = 1 ;:::; n and = 1 ;:::; n andthereexistsa k suchthat i = i forall i k .Let =0 ; 0 ;:::; k )]TJ/F15 11.9552 Tf -422.702 -23.084 Td [(1 ; k +1 )]TJ/F15 11.9552 Tf 12.536 0 Td [(1 ;:::; n )]TJ/F15 11.9552 Tf 12.536 0 Td [(1= ; 0 ;:::; k )]TJ/F15 11.9552 Tf 12.536 0 Td [(1 ; k +1 )]TJ/F15 11.9552 Tf 12.536 0 Td [(1 ;:::; n )]TJ/F15 11.9552 Tf 12.536 0 Td [(1 2 Z n 0 .Let R 1 = k [ X ] = h X i and R 2 = k [ X ] = h X i .Then R 1 = R 2 ifandonlyif k [ X ] = h X )]TJ/F34 7.9701 Tf 6.586 0 Td [( i =

PAGE 22

19 k [ X ] = h X )]TJ/F34 7.9701 Tf 6.587 0 Td [( i .Thatis, R 1 = R 2 ifandonlyif k [ X 1 ;:::;X k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 i = k [ X 1 ;:::;X k )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.757 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i Proof. Let I = h X i and J = h X i .Assumerstthatwehavethat R 1 = R 2 ,then itfollowstriviallythat I = J .Considertheideals h X 1 1 ;:::;X n n ;X n i = h I;X n i = h X 1 1 ;:::;X n )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ;X n i = I 1 and h X 1 1 ;:::;X n n ;X n i = h J;X n i = h X 1 1 ;:::;X n )]TJ/F32 5.9776 Tf 5.757 0 Td [(1 n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ;X n i = J 1 .Weaddedtheexactsametermstoeachidealbyreducingtheexponenton X n downto1ineachideal'sgeneratingset,soitfollowsdirectlythat I 1 = J 1 .Continuing inthismanner,wegetthefollowingchainsofideals: I I 1 I n )]TJ/F34 7.9701 Tf 6.587 0 Td [(k +1 = = = J J 1 J n )]TJ/F34 7.9701 Tf 6.587 0 Td [(k +1 Byconstruction, h X )]TJ/F34 7.9701 Tf 6.586 0 Td [( i = I n )]TJ/F34 7.9701 Tf 6.587 0 Td [(k +1 = J n )]TJ/F34 7.9701 Tf 6.586 0 Td [(k +1 = h X )]TJ/F34 7.9701 Tf 6.587 0 Td [( i ,andtherefore, k [ X ] = h X )]TJ/F34 7.9701 Tf 6.586 0 Td [( i = k [ X ] = h X )]TJ/F34 7.9701 Tf 6.587 0 Td [( i ,asrequired. Conversely,suppose k [ X ] = h X )]TJ/F34 7.9701 Tf 6.587 0 Td [( i = k [ X ] = h X )]TJ/F34 7.9701 Tf 6.587 0 Td [( i .Wehavethat k [ X ] = h X )]TJ/F34 7.9701 Tf 6.587 0 Td [( i = k [ X ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ;X k ;:::;X n i = k [ X 1 ;:::;X k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 i = k [ X 1 ;:::;X k )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.757 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i .Welet R 0 1 = k [ X 1 ;:::;X k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.757 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 i and R 0 2 = k [ X 1 ;:::;X k )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i .Wecanmodifythesebyconsidering R 1 1 = k [ X 1 ;:::;X k ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ;X k k i and R 1 2 = k [ X 1 ;:::;X k ] = h X 1 1 ;:::;X k )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ;X k k i Bythehypotheses, k = k andthus,wehavetriviallythat R 1 1 = R 1 2 .Continuingin thismanner,wegetasimilarchainasbefore: R 0 1 R 1 1 !! R n )]TJ/F34 7.9701 Tf 6.586 0 Td [(k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 1 = = = R 0 2 R 1 2 !! R n )]TJ/F34 7.9701 Tf 6.586 0 Td [(k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 2 Thus,wehave R 1 = R n )]TJ/F34 7.9701 Tf 6.586 0 Td [(k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 1 = R n )]TJ/F34 7.9701 Tf 6.586 0 Td [(k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 2 = R 2 arerequired. TheunderlyingideaofLemma5.5isthatifwearecomparingtwopolynomial factorringsoftheformwehavebeenstudying,andanyoftheexponentsoftheideal

PAGE 23

20 generatorsarethesame,thenwehavethetoolsrequiredtoallowustoignorethose variables.Thisbecomescriticalinournexttheorem. Theorem5.1. Suppose R 1 = k [ X ] = h X i and R 2 = k [ X ] = h X i ,then )]TJ/F34 7.9701 Tf 7.315 -1.793 Td [(a R 1 = )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(a R 2 ifandonlyif R 1 = R 2 Proof. Sincethealgorithmforcreatingtheannihilatorgraphisclearlywelldened, R 1 = R 2 implies)]TJ/F34 7.9701 Tf 47.049 -1.793 Td [(a R 1 = )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R 2 Fortheconversedirection,wewishtoshowthatif R 1 6 = R 2 ,then)]TJ/F34 7.9701 Tf 45.251 -1.793 Td [(a R 1 6 = )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R 2 .Sincewemaypermutethevariablesandthus,theexponents,ofeither ring,itispossibletorearrangethevariablesin h X i and h X i suchthatifany i = j ,thentheycanbeplacedintherightmostpositionsafterpermuting.If i = j ,assumewithoutlossofgeneralitythat n = n ,thenbyvirtueofLemma 5.5,wemayreplace R 1 with R 0 1 = k [ X 1 ;:::;X n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ] = h X 1 1 ;:::;X n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i and R 2 with R 0 2 = k [ X 1 ;:::;X n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ] = h X 1 1 ;:::;X n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i .Continuinginthisway,wemayassume that R 1 and R 2 aresuchthat i 6 = j forall i;j Furthermore,wemayalsoassumethat j )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(a R 1 j = j )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(a R 2 j becauseiftheyweren't equal,theyclearlywouldnotbeisomorphic.Sincethevertexwithlargestdegreein eachgraphhasdegreeonelessthanthesizeofthegraph,andeachgraphhasthe samesize,weknowtheirhighestdegreeverticeshavethesamedegrees.Weproceed byshowingthattheverticesofsecondhighestdegreehavenonequaldegreesineach graph. Let k besuchthat k i forall i ,andwithoutlossofgenerality,let k > j for all j .Suppose k = x k )]TJ/F31 7.9701 Tf 6.587 0 Td [(2 k Q i 6 = k x i )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 i ; = Q n i =1 x i )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 i anddeg[ ]= .Weseethat deg[ k ]= )]TJ/F33 11.9552 Tf 12.016 0 Td [( k forsome k .ByLemma5.4, k > 0.Todetermine k ,noticethat k isexactlythenumberofantichainsthatannihilate butdonotannihilate k .If welet B = f A 2 M I j x k 2 A g ,then k = jf A [f x k gj A 2 B gj = j B j .Let f A [f x i gj A 2 B g = B i forageneric i .Wewishtolookspecicallyat B k Sincewecansaythat k > j forall j ,themaximal i ,whichis k ,corresponds totheminimal B i ,whichis B k .Wehavethat B k isequaltothenumberofantichains

PAGE 24

21 notcontaining x k ,therefore,itisdirectlydependentonthesizeoftheposet Z 1 Z k )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 Z k +1 Z n .Thisisbecauseoftheclearcorrespondencebetween theexponentsofelementsin M I andtheset Z 1 Z n ;antichainsof M I can bemappeddirectlytoantichainsof Z 1 Z n .Moreimportantly,antichains of M I thatdonotcontain x k canbemappeddirectlytoantichainsof Z 1 Z k )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 Z k +1 Z n .Thisposetisclearlyminimizedwhen k islargest. Weconstructasimilarmonomial j in R 2 usingthemaximalexponentofthe i s, whichis j .Thenweseethat j representsthevertexofsecondhighestdegree in)]TJ/F34 7.9701 Tf 22.079 -1.793 Td [(a R 2 .Byconstruction,wehave j B k j < j B j j ,thus,for[ k ] 2 V )]TJ/F34 7.9701 Tf 11.866 -1.793 Td [(a R 1 and [ j ] 2 V )]TJ/F34 7.9701 Tf 11.867 -1.794 Td [(a R 2 ,deg[ k ]= )-241(j B k j > )-241(j B j j =deg[ j ].Hence,thevertexof secondhighestdegreein)]TJ/F34 7.9701 Tf 136.834 -1.793 Td [(a R 1 hasstrictlylargerdegreethanthevertexofsecond highestdegreein)]TJ/F34 7.9701 Tf 97.775 -1.793 Td [(a R 2 ,and)]TJ/F34 7.9701 Tf 41.782 -1.793 Td [(a R 1 6 = )]TJ/F34 7.9701 Tf 7.315 -1.793 Td [(a R 2 asrequired. Intheprevioustheorem,weletthemonomialidealbegeneratedspecicallyby singlevariablesraisedtopowers.Ifweconsiderthemonomiallatticeoftheseideals, wegetan n -dimensionalboxwithauniquepointthatisfarthestfromtheorigin withrespecttoEuclideandistance.Ifweaddageneratortotheidealthatisa monomialcontainingmorethanonevariable,asocalledmixedmonomial,wedonot maintainthisnicestructure.Thisresultsinmorethanonemonomialhavingthe sameannihilatorasseeninthefollowingexamples. Example5.8. Let R = k [ X;Y ] = h X 5 ;Y 5 ;X 3 Y 3 i ,thenwecanconsideravisualrepresentationofthemonomialsin R .Wecantakeanintegerlattice,andletthepoints inthelatticerepresenttheexponentsofthevariablesinthemonomials.Wecallthis representationthemonomiallatticeandshowtheoneassociatedwith R :

PAGE 25

22 Weseethatthelocationinthelatticeofthepoints x 2 y 4 and x 4 y 2 causesAnn x 2 y 4 = P M I =Ann x 4 y 2 .Inlowdimensions,thispropertyiseasytosee.Inhigherdimensions,wegetthefollowingdenitionandresults. Denition5.5. In R = k [ X ] =I where I isamonomialideal,wesayacornerisany monomial, 2M I ,suchthat x i =0forall i .Assuch,Ann = P M I Example5.9. Inthering k [ X;Y;Z ] = h X 8 ;Y 8 ;Z 8 ;X 6 Y 6 Z 6 i ,wecanconsiderthe monomiallatticeasapolytopewithintegervertices.Themonomialsin M I would bealltheintegerlatticepointsinsidethepolytope,oronthefacescreatedbythe axes,excludingtheorigin.Here,thecornershaveaclearvisualrepresentation.That is,thethreecornersinthepolytopeare ; 7 ; 7 ; ; 7 ; 5and ; 5 ; 7.Thepointsthat arenotcontainedintheinteriorofthepolytope,orareontheedgesorfacescreated bytheaxes,areallpointsthatare0intheideal h X 8 ;Y 8 ;Z 8 ;X 6 Y 6 Z 6 i

PAGE 26

23 Denition5.6. Aproperideal I ofthering k [ X ]issaidtobeArtinianifandonly ifthegeneratorsof I include X i i forall i with i 2 Z > 0 Lemma5.6. Suppose R = k [ X ] =I where I isArtinian,thenin )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R ,theantichains madefromthesetofcornersareinthesameequivalenceclass,andrepresentthe vertexwithmaximaldegree.Furthermore,for acorner,and x k thevariablewith largestexponentin ,if x k k = ,then deg[ k ] issecondhighestin )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(a R Proof. Itfollowsfromthedenitionofacornerthatallcornershavethesameannihilators.Consequently,sincetheannihilatorofasetistheintersectionofthe annihilatorsoftheelementsofthatset,theannihilatorsofalltheantichainscreated bythecornersisalsothesame.Specically,thisannihilatoris P M I .Assuch,this vertexhasmaximaldegree,andinfactisadjacenttoeveryothervertexinthegraph. Wemustshowthattheredoesnotexistavertex[ A ]suchthat .2deg[ k ] < deg[ A ] < deg[ ] Supposedeg[ ]= anddeg[ k ]= )]TJ/F33 11.9552 Tf 12.23 0 Td [( k .WeseeasintheproofofLemma5.4 that k isequaltothenumberofantichainsthatdonotcontain x k .Thisnumber isclearlyminimizedwhenever x k hasthelargestexponentbythesameargumentas before.Thus,if A existedasin.2,itcouldnotbeamonomial,henceiswould havetobeanantichainofsizegreaterthan1.However,thisisnotpossibleeither, forif A = f 1 ;:::; m g ,then,byrepeatingtheargumentfromtheproofofLemma 5.4,Ann A = n i =1 Ann i impliesAnn A Ann i forall i .Thisimpliesthat deg[ A ]= j Ann A jj Ann i j =deg i forall i .Thisreturnsustothe casewecoveredalready,andthuscontradictsequation.2,asrequired. Beforewemoveontomoregeneralgraphs,letusrstconsideramonomialideal thatisnotArtinian.

PAGE 27

24 Denition5.7. Givenamonomialideal I = h X 1 1 ;:::;X s s ; 1 ;::: t i ofaring R = k [ X ]where i = Q x k k and s n ,wedenetheArtinianClosure ^ I of I as ^ I = h I;X 1 +1 1 ;:::;X n +1 n i where X =LCM X 1 1 ;:::;X s s ; 1 ;:::; t NotethatLCMisthestandardleastcommonmultipleofasetofmonomials.In Section7,wewillproveinCorollary7.1thatthereexistsacanonicalsetofgenerators for I ,soeventhoughmultiplegeneratingsetsexistforagivenideal I ,whenreferring tothegeneratingsetof I ,wewillusethiscanonicalset.Sincethiscanonicalsetexists, wewillrefertoLCM I foramonomialidealtobetheLCMofthosegenerators. Example5.10. Let R = k [ X;Y;Z ]andlet I beanidealof R suchthat I = h X 4 ;X 3 Y;Y 2 Z 4 i .Thentheleastcommonmultipleofthegeneratorsis X 4 Y 2 Z 4 Thus,theArtinianclosureof I is h X 4 ;X 3 Y;Y 2 Z 4 ;X 5 ;Y 3 ;Z 5 i = h X 4 ;Y 3 ;Z 5 ;X 3 Y;Y 2 Z 4 i Theorem5.2. Let R = k [ X 1 ;:::;X n ] ,and I R amonomialidealof R with Artinianclosure ^ I ,then j )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(a R= ^ I jj )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(a R=I j Beforeweprovethistheorem,anexampleisinorder.Sinceitisclearthat I = ^ I ifandonlyif I isArtinian,thistheoremisonlyappliednontriviallytocaseswhere I isnotArtinian.Sincewehaven'tseenanexampleofthisyet,wewilldothatnow. Example5.11. Let R = k [ X;Y;Z ] =I where I = h X 3 ;Y 2 ;X 2 Z 2 i .Wewillproceed byshowing j M I j = j M ^ I j ,where M I isthesetofmonomialsin R whichhave distinctannihilators.Sincethevertexsetof)]TJ/F34 7.9701 Tf 236.393 -1.793 Td [(a R isexactlythesetofantichainsof monomialswithdistinctannihilators,showingthat j M I j = j M ^ I j isidentical tothestatementofthetheorem. Byourdenition, M I isinnite,butwewillseethat M I isnite.Wehave M I = f x;x 2 ;y;z;z 2 ;xy;x 2 y;xz;xz 2 ;x 2 z;yz;yz 2 ;xyz;x 2 yz g[f z k ;xz k ;yz k ;xyz k ;x 2 yz k j k> 2 g

PAGE 28

25 However,wecanseethat M I isnitebynoticingthefollowing:Ann z 2 =Ann z k Ann xz 2 =Ann xz k ,Ann yz 2 =Ann yz k ,Ann xyz k =Ann xyz 2 andAnn x 2 yz k = Ann x 2 yz 2 forall k 2.Thus, M I = f x;x 2 ;y;z;z 2 ;xy;x 2 y;xz;xz 2 ;x 2 z;yz;yz 2 ;xyz;x 2 yz g Werstshow jM I j = jM ^ I j ,byrstcalculatingLCM I .Itiseasytoseethat LCM I = X 3 Y 2 Z 2 ,whichisjustthehighestpowerofeachvariablethatispresent. AsperDenition5.7, = ; 2 ; 2andtherefore, ^ I = h I;X 4 ;Y 3 ;Z 3 i = h X 3 ;Y 2 ;Z 3 ;X 2 Z 2 i Fromhere,itiseasytoseethat jM I j = jM ^ I j .Butnoticethattheonlydierence betweenthetwosetsisthemonomial z 2 in M ^ I isassociatedwiththemonomial z k in M I .Sincetheseelementshavethesameannihilatorsfor k 2,though,itisclear thattheantichainstructureisthesame.Therefore, j M I j = j M ^ I j WeproceednowwiththeproofofTheorem5.2. Proof. Inthisproof,foreaseofnotation,wewillshowthegeneralcasewhereonly onevariableisunbounded,anditwillbeeasytoseethattheresultholdsforany numberofunboundedvariables. Suppose I = h X 1 1 ;:::;X n )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ;X n n i isanidealof R = k [ X 1 ;:::;X n ]where is anymixedmonomialnotcontaining X n .Wemayassumethat X n ispartofamixed monomialgeneratorof I becauseifitwerenot,thenAnn x n 2; ,and X n wouldn't contributeanythingtotheannihilatorgraph.Let X n = f x n ;x 2 n ;:::;x k n ;::: g ,then weseethat X n M I andalsothatAnn x k n = P f 2M I j j g forall k n Thus,if X n = f x n ;x 2 n ;:::;x n n g ,only X n M I .Thatis,onlythepowersof x n whichremainaftertheadditionof X n +1 n tothegeneratorsof I willbein M I ,which ispreciselywhatoccursintheArtinianclosureof I .

PAGE 29

26 Ifthereismorethanonemixedmonomialcontaining X n ,theLCMofthegenerators willconsideronlythehighestpowerof X n ,andtheresultstillholds.Ifthereismore thanoneunboundedvariable,wesimplyrepeattheargumentwitheachunbounded variable.ThereisapossibilitythatforlargeridealsthaninExample5.11,upon additionofgeneratorsintheArtinianclosureof I ,wemayincreasethenumber ofcornersinthepolytoperepresentingthemonomialideal.Ifthishappens,then thosecornerswillcollapseintoonepoint.Thus,wehavethat jM ^ I jjM I j ,and bytheargumentgiveninExample5.11, j M ^ I jj M I j .Thus,wehavethat j )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R= ^ I jj )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(a R=I j InalltheprecedingtheoremsinSection5,thereadermayhavenoticedthatnearly everyidealwaseitherArtinian,orweuseditsArtinianclosure.Thisisbecause experimentaldatasuggeststhattheuniquenessofthegraphscouldfailforfactor ringswheretheidealisnotArtinian.Thisisextremelydiculttoshow,though,due tothecomplexityoftheantichaincalculations.Experimentaldataalsosuggeststhat inthecaseofthering k [ X ] = h X ; 1 ;:::; s i where i aremixedmonomialgenerators, thatwestillmaintainuniquenessoftheannihilatorgraph.InLemma5.6,weshowed whatthevertexofsecondhighestdegreelookedlike,anditisconjecturedthata proofverysimilartotheproofofTheorem5.1existsforshowinguniquenessofthe moregeneralrings.Thereiscontinuingresearchintheareaofantichains,however, sotheopportunitiesforfutureresearchabound.Weusetheresultsfromthissection toleadusintothenextsection. 6. MonomialAnnihilatorGraph Inthelastsection,weintroducedtheannihilatorgraphofaring.Wewereableto showthattheannihilatorgraphuniquelydeterminesringsoftheform k [ X ] =I where I isArtinian.Therewasanoticeablelackofexamples,though.Thisisbecauseofthe needtogeneratealltheantichainsof M I .Inpractice,thisistediousandthereisnot asystematicwaytodoit,noristhereformulatoevengiveanumberofantichainsin

PAGE 30

27 thegeneralcase.Theserestrictionsleadustotrytondsomethingbetter.Inthis section,wewillusetheideaoftheannihilatorgraphasmotivationtostudyasimpler graphwithmanyofthesameproperties.Inthecaseofidealsoftheform h X i ,this newgraphwillactuallybeasubgraphoftheannihilatorgraph. Denition6.1. Givenaring R = k [ X ] =I where I isamonomialidealof k [ X ], weassociateto R agraph,)]TJ/F34 7.9701 Tf 54.867 -1.794 Td [(m R suchthat V )]TJ/F34 7.9701 Tf 11.867 -1.794 Td [(m R = M I .Forall ; 2M I 2 E )]TJ/F34 7.9701 Tf 11.866 -1.793 Td [(m R if =0in R .Wecallthisgraphthemonomialannihilatorgraph of R ,orjustmonomialgraphwhenitisclearfromthecontextwhatismeant. Noticethatbythisdenition,itispossibletohavetwoverticeswhichrepresentthe sameequivalenceclassundertherelationdenedinProposition5.2.Forexample, intheannihilatorgraph,thesetofcornerswasrepresentedbyasinglevertexin thegraph,butinthemonomialgraph,eachcornerwillhaveit'sownvertexdespite havingequalannihilators. Wehaveasimilarsetoftheoremsforthemonomialgraphsaswedidforthe annihilatorgraphs.Webeginwithanexample. Example6.1. Let R = k [ X;Y;Z ] = h X 3 ;Y 2 ;Z 2 i .Whenwecalculatethesetofmonomials,weget M I = f x;x 2 ;y;z;xy;x 2 y;xz;x 2 z;yz;xyz;x 2 yz g .Then)]TJ/F34 7.9701 Tf 46.334 -1.793 Td [(m R is

PAGE 31

28 Weseefromthefollowingexamplethatwedonothavetheuniquenessresultsfor rings. Example6.2. Let R = k [ X;Y ] ;I = h X 3 ;Y 2 ;X 2 Y i and J = h X 3 ;Y 3 ;XY i .Since theseareclearlynonisormophic,wecanmoveontothemonomialgraphsof R 1 and R 2 .Weproceedbyconstructingthemonomialgraphsof R 1 and R 2 ,whichare Thus,)]TJ/F34 7.9701 Tf 40.221 -1.793 Td [(m R 1 = )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R 2 = K 4 Thisexamplecanbeexpandedforanicecomparisonbetweenthezerodivisor graph,andthemonomialgraph. Proposition6.1. Forany n 2 Z > 0 ,thereexistsan R = k [ X ] =I suchthat )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R = K n Proof. Let R = k [ X 1 ;:::;X n ] = h X 2 1 ;:::;X 2 n ;X 1 X 2 ;X 1 X 3 ;:::;X n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 X n i .Then M I = f x 1 ;:::;x n g andforevery i;j 1 i;j n ,[ x i ] ; [ x j ] 2 E )]TJ/F34 7.9701 Tf 11.867 -1.794 Td [(m R ,thus,)]TJ/F34 7.9701 Tf 54.067 -1.794 Td [(m R = K n Notethatthetypesofringswhichhavecompletezerodivisorgraphsasstated inTheorem4.4diervastlyfromthetypesofringsthathavecompletemonomial graphs.

PAGE 32

29 Proposition6.2. Suppose R = k [ X ] =I and I isamonomialidealof k [ X ] where I 6 = h 1 i ,then )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R isaconnectedsubgraphof \050 R Proof. Since I 6 = h 1 i ,then R containszerodivisors,andthereforeisinnite,andnot anintegraldomain.Thus,byTheorem4.1,wehavethat\050 R isinnite.Bythe denitionof)]TJ/F34 7.9701 Tf 71.762 -1.794 Td [(m R ,wehavethat V )]TJ/F34 7.9701 Tf 11.867 -1.794 Td [(m R Z R = V \050 R .Sincetheedgesare denedidenticallyineachgraph,wehavethat)]TJ/F34 7.9701 Tf 250.213 -1.793 Td [(m R \050 R Toseethat)]TJ/F34 7.9701 Tf 68.864 -1.794 Td [(m R isconnected,noticethat M I Z R .Weshowedintheproof ofTheorem4.2thatwhentheedgesaredenedastheyareinthemonomialgraph, anytwozerodivisorsareconnected.Thuswehavethat)]TJ/F34 7.9701 Tf 300.809 -1.793 Td [(m R isconnected. Remark 6.1 Noticethatinadditiontothegraphbeingconnected,wealsohaveat leastonevertexthatisadjacenttoeveryothervertexinthegraph.Namely,these verticesarethoserepresentedbymonomialswhicharecornersinthemonomiallattice, asdescribedinSection5.ThisisinstarkcontrastwithTheorem4.3inthatevery monomialgraphhasauniversalpoint,butonlyaveryspecicringwillyieldazero divisorgraphwithauniversalpoint. Denition6.2. Let R = k [ X ] =I .Ifwehaveavariableraisedtoapower, x i i 2 R thenwedenethe deltasetof x i i as x i i = f 2M I j x i i =0 g Proposition6.3. Let R = k [ X ] = h X i ,where = 1 ;:::; n 2 Z n > 0 thenwehave thefollowingproperties: j V )]TJ/F34 7.9701 Tf 11.866 -1.794 Td [(m R j = Q i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 deg[ x i i ]= 8 > > > < > > > : i Y i 6 = j i ; i < i 2 i Y i 6 = j i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; i i 2 For = Q x i i deg[ ]= 8 < : j[ x i i j ; i < i 2 8 i j[ x i i j)]TJ/F15 11.9552 Tf 17.933 0 Td [(1 ;else

PAGE 33

30 Proof. Thesizeofthevertexsetof)]TJ/F34 7.9701 Tf 181.946 -1.793 Td [(m R isexactlythesizeof M I ,thenumber ofmonomialsin R .Sinceeachmonomialin M I isoftheform Q x i i ,and thereare i choicesforeach i ,thenitisclearthatafterwesubtractoutthe monomial1,thesizeofthevertexsetistheproductofthe i 's. Tocalculatethedegreeofavariableraisedtoapower,wemustlookatwhat annihilatesit.Weseethat x i )]TJ/F34 7.9701 Tf 6.587 0 Td [( i i willannihilate x i i ,aswill x i )]TJ/F34 7.9701 Tf 6.587 0 Td [( i + k i for 0 k i )]TJ/F15 11.9552 Tf 12.522 0 Td [(1.Inadditiontothe i choicesforthepowerof x i ,wehave j choicesforallthe x j 's.Noticehoweverthatwhen i i 2 ,theformula willcount x i i asbeingadjacentwithitself,whichwearenotallowing,sowe subtract1toaccountforthat. Toprovethis,let 2M I suchthat =0,then isadjacentto .Since =0,thereisatleastonevariable, x i suchthatthesumofthepowerof x i in plusthepowerof x i in isgreaterthanorequalto i .Consequently, 2 x i i forthatspecic i ,andingeneral, 2[ n i =1 x i i .Nowassume 2[ n i =1 x i i ,then necessarilyannihilatesoneofthevariablesin ,and therefore, =0.Thus,everythingthatannihilates isintheunionof thedeltasets,andeverythingintheunionofthedeltasetsannihilates ,as required.Asinpart,ifanyofthe i 'sarehalformoreofthe i ,then themonomialwillappearinit'sowndeltaset,andmustberemoved,sowe subtract1inthatcase. Example6.3. Let R = k [ W;X;Y;Z ] = h W 4 ;X 5 ;Y 3 ;Z 3 i .WeuseProposition6.3to calculatedeg[ x 3 y 2 z 2 ].Frompart3,wehavedeg[ x 3 y 2 z 2 ]= j x 3 [ y 2 [ z 2 j Bytheprincipalofinclusion/exclusion,inordertocalculatedeg[ x 3 y 2 z 2 ],wemust

PAGE 34

31 performthecalculation: j x 3 j + j y 2 j + j z 2 j)]TJ/F15 11.9552 Tf 15.926 0 Td [( j x 3 y 2 j + j x 3 z 2 j + j y 2 z 2 j + j x 3 y 2 z 2 j)]TJ/F15 11.9552 Tf 15.925 0 Td [(1 Weproceedbycalculatingthepiecesnow: j x 3 j = jf w 1 x 2 y 3 z 4 j 2 2f 2 ; 3 ; 4 g 0 i < i 8 i 6 =2 gj =3 3 3 4=108 j y 2 j = jf w 1 x 2 y 3 z 4 j 3 2f 1 ; 2 g 0 i < i 8 i 6 =3 gj =2 5 3 4=120 j z 2 j = jf w 1 x 2 y 3 z 4 j 4 2f 1 ; 2 g 0 i < i 8 i 6 =4 gj =2 5 3 4=120 j x 3 y 2 j = jf w 1 x 2 y 3 z 4 j 2 2f 2 ; 3 ; 4 g ; 3 2f 1 ; 2 g 0 i < i ;i 2f 1 ; 4 ggj = 4 3 2 3=72 j x 3 z 2 j = jf w 1 x 2 y 3 z 4 j 2 2f 2 ; 3 ; 4 g ; 4 2f 1 ; 2 g 0 i < i ;i 2f 1 ; 3 ggj = 4 3 2 3=72 j y 2 z 2 j = jf w 1 x 2 y 3 z 4 j 3 2f 1 ; 2 g ; 4 2f 1 ; 2 g 0 i < i ;i 2f 1 ; 2 ggj = 4 5 1 1=80 j x 3 y 2 z 2 j = jf w 1 x 2 y 3 z 4 j 2 2f 2 ; 3 ; 4 g ; 3 2f 1 ; 2 g ; 4 2f 1 ; 2 g ; 0 1 < 4 gj =3 1 1 4=12 Combiningeverything,wehave deg[ x 3 y 2 z 2 ]=108+120+120 )]TJ/F15 11.9552 Tf 11.955 0 Td [(+72+80+48 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1=171 Remark 6.2 Thisexampleisclearlyextremelycumbersomeifonewantedtodorapid calculations,butitisalsoeasilyprogrammable.Theabovecalculationwasconrmed usingaMATLABprogram,andthesourcecodeforthatprogramwillbegivenlater. ThesourcecodegivenintheMATLABprogramisonlyformonomialsin4variables, butcaneasilybewrittenfor n variables.Furthermore,formorecomplicatedrings, onecanusethebuiltinfunctioninCoCoAtocalculatetheHilbertseriesoftheideal. Thisfunctioncountsthenumberofpointsinthemonomiallattice,andwilleven givethenumberofmonomialsofagiventotaldegree.Thealgebraicdetailsofthe Hilbertseriesarefarbeyondthescopeofannihilatorgraphs,though,andwillnotbe discussedhere.Theinterestedreadercanreferto[5],Chapter9, x 3.

PAGE 35

32 Lemma6.1. Let R = k [ X ] = h X i ,thenavertexofleastdegreein )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R isrepresentedby x k ,where k isthegreatestofthe i 's. Proof. Werstconrmthatthevertexofleastdegreeisasinglevariableraisedto apowerasitwillturnoutinthiscase,thatpoweris1.Let = x i x j forsome i;j .Thenweseethatdeg[ ] deg[ x j ].Thisisbecauseofmonomialslike x i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i Since x i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i =0,and x i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i x j 6 =0,thereisatleastonevertexthat[ ]isadjacent tothat[ x j ]isnot,whereaseveryvertexadjacentto[ x j ]isadjacentto[ ].Thus,for anymixedmonomial,thereisasinglevariablewithasmallerdegree. Next,weshowthatif k =max i f i g ,thendeg[ x k ] deg[ x i ]forall i .Since itisclearthatdeg[ x k ]= Q i 6 = k i ,and k i forall i ,thenclearlydeg[ x k ]is minimal. Theorem6.1. Let R 1 = k [ X ] = h X i and R 2 = k [ X ] = h X i ,then R 1 = R 2 ifandonly if )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R 1 = )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R 2 with ; 2 Z n > 0 Proof. Sincethealgorithmforgeneratingthemonomialgraphisclearlywelldened, wehavetriviallythat R 1 = R 2 implies)]TJ/F34 7.9701 Tf 47.731 -1.794 Td [(m R 1 = )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(m R 2 .Weproceedbyproving that)]TJ/F34 7.9701 Tf 32.677 -1.793 Td [(m R 1 6 = )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R 2 implies R 1 6 = R 2 Asinthecaseoftheannihilatorgraphs,wemayassumetwothingsaretrue: Theredoesnotexist i;j suchthat i = j Q i = Q i Ifwerefalse,byvirtueofLemma5.5wecouldreplace R 1 with R 0 1 and R 2 with R 0 2 where R 0 1 and R 0 2 donothaveanyequalexponentsintheirideals.Bythesame argumentofLemma5.5,if R 1 6 = R 2 ,thentheconstructed R 0 1 and R 0 2 wouldnotbe isomorphic,either,sotheLemmastillapplieshere.Ifwerefalse,thenthegraphs wouldbedierentsizes,andtheresultwouldfollow. FromLemma6.1,weseethatthevertexofleastdegreein)]TJ/F34 7.9701 Tf 301.285 -1.793 Td [(m R 1 isrepresentedby x k where k =max i f i g ,andsimilarly,weget x l in)]TJ/F34 7.9701 Tf 21.362 -1.793 Td [(m R 2 ,where l =max i f i g Byassumption, k 6 = l andwithoutlossofgenerality,wewilllet k > l .

PAGE 36

33 Then,fromassumption,deg[ x k ]= Q i 6 = k i < Q j 6 = l j =deg[ x l ].Thus,the verticesofleastdegreein)]TJ/F34 7.9701 Tf 139.637 -1.793 Td [(m R 1 and)]TJ/F34 7.9701 Tf 38.21 -1.793 Td [(m R 2 arenotequal,thusthegraphsarenot isomorphic. Beforewemoveontomoregeneralannihilatorgraphs,wewillproveonemore importantfactaboutthesebasicmonomialgraphs:thattheyhaveaHamiltonian path.Todothis,weneedtodeneamap, f .Wewillrstseeanexampleofthe map,andthenseethegeneraldenition. Example6.4. Considertheorderedtriple = ; 4 ; 3,andthespace Z = Z 3 Z 4 Z 3 .Ifweconsider c = c 1 ;c 2 ;c 3 2 Z ,wecandemonstrateaonetoone correspondencebetweentheelementsof Z andtheelementsof Z 36 where36=3 4 3, withthefollowingtables: c 3 =0 012 0 012 1 345 2 678 3 91011 c 3 =1 012 0 121314 1 151617 2 181920 3 212223 c 3 =2 012 0 242526 1 272829 2 303132 3 333435 Withthiscorrespondence,wehaveamap f : Z )167(! Z 36 Wereadthemapasfollows:fortheelement c = ; 3 ; 2,welookrstat c 3 =2, andgotothethirdtable.Thenwelookfortheorderedpair c 1 ;c 2 = ; 3,which isreadwith c 1 beingthecolumn,and c 2 beingtherow,inthattableandseethat f ; 3 ; 2=34.Wecanalsousethemapbackwards.Ifwewishtond f )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 wend27inthetables,andnoticethatitisinthetablefor c 3 =2andorderedpair ; 1,so f )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 = ; 1 ; 2.Notethatthecolumnwasreadrstwhenndingthe orderedpair. Wecannowstatethemapinfullgenerality.

PAGE 37

34 Proposition6.4. If = 1 ;:::; n and A = Q n i =1 i ,wedene f suchthat f : Z )167(! Z A f c 1 ;:::;c n = n X i =1 c i i )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 Y j =1 j withtheconventionthat Q 0 j =1 j =1 ,then f isabijection. For a;b 2 Z ,if f a + f b A ,thenthereexistsan i suchthat a i + b i i Proof. Suppose a;b 2 Z a = a 1 ;:::;a n b = b 1 ;:::;b n and f a = f b .We mustshowthat f a )]TJ/F33 11.9552 Tf 11.955 0 Td [(f b =0implies a = b Let .10= a 1 )]TJ/F33 11.9552 Tf 11.955 0 Td [(b 1 + a 2 )]TJ/F33 11.9552 Tf 11.955 0 Td [(b 2 1 + + a n )]TJ/F33 11.9552 Tf 11.955 0 Td [(b n 1 n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 asperthedenitionof f .Multiplybothsidesof.1by 2 3 n .Inthe imageof f Q n i =1 i = A =0,soafterthemultiplication,wehave .20= a 1 )]TJ/F33 11.9552 Tf 11.955 0 Td [(b 1 2 n Since 2 n 6 =0,then a 1 = b 1 Wecanrepeatthisprocesstogetasimilarresultfor a 2 and b 2 asfollows: by.2, a 1 )]TJ/F33 11.9552 Tf 12.214 0 Td [(b 1 =0.Usethiswith.1tocancelouttherstterm,and wehave .3 a 2 )]TJ/F33 11.9552 Tf 11.955 0 Td [(b 2 1 + + a n )]TJ/F33 11.9552 Tf 11.956 0 Td [(b n 1 n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 Multiplyingbothsidesof.3by 3 n zerosouteverytermexcept a 2 )]TJ/F33 11.9552 Tf -384.955 -23.084 Td [(b 2 1 3 n ,whichagainimplies a 2 = b 2 .Continuinginthismanner,we

PAGE 38

35 canshow a k = b k onthe k th stepbytaking 0= a k )]TJ/F33 11.9552 Tf 11.955 0 Td [(b k 1 k )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 + + a n )]TJ/F33 11.9552 Tf 11.955 0 Td [(b n 1 n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 andmultiplyingbothsidesby k +1 n toyield a k )]TJ/F33 11.9552 Tf 11.956 0 Td [(b k 1 k )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 k +1 n =0 andthus, a k = b k .Therefore, a = b asrequired.Thefactthat f isabijection followssince j Z j = j Z A j and f isonetoone. Todothis,assumethestatementisfalse,thenforall i a i + b i i )]TJ/F15 11.9552 Tf 11.101 0 Td [(1.Then wehave f a + f b = n X i =1 a i + b i i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 Y j =1 i Since a i + b i i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1,wehavebythehypothesisthat n X i =1 i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 i )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 Y j =1 i f a + f b n Y i =1 i Thisgivesus 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 1 + 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 1 2 + + n )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 1 n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 whichsimpliesto 1 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1+ 1 2 )]TJ/F33 11.9552 Tf 11.955 0 Td [( 1 + 1 2 3 )]TJ/F33 11.9552 Tf 11.955 0 Td [( 1 2 + + n Y i =1 i )]TJ/F34 7.9701 Tf 11.955 14.944 Td [(n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 Y i =1 i n Y i =1 i However,thistelescopesandgivesus n Y i =1 i )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 n Y i =1 i whichisclearlyacontradiction.Thus,wehavethatthereexistsatleastone i suchthat a i + b i i

PAGE 39

36 NoticethatfromExample6.4, f ; 3 ; 2=0+1 3+2 4=27or,more generally, f ; 3 ; 2=0+1 1 +2 1 2 =27. Theorem6.2. If R = k [ X ] = h X i with 2 Z n > 0 ,then )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(m R hasaHamiltonian path. Proof. Recallthatthereisaonetoonecorrespondencebetweenthemonomialsof M I andtheelementsof Z )-223(f ;:::; 0 g inthecasewhere I isArtinian,asitishere. Consequently,wecanuse f tosetupthesamebijectionbetween Z )-255(f ;:::; 0 g andtheelementsof M I aswedidwith Z )-158(f ;:::; 0 g and Z A where A = Q n i =1 i Forexample,theelement a;b;c mightmapto d under f ,sothemonomial x a 1 x b 2 x c 3 wouldbeassociatedwith d .Withthis,wesetupthefollowingsequenceofnumbers in Z A : 1 ;A )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; 2 ;A )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 ; 3 ;A )]TJ/F15 11.9552 Tf 11.955 0 Td [(3 ;::: andconsiderthesequenceofelementsin Z : f )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ;f )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 A )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ;f )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ;f )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 A )]TJ/F15 11.9552 Tf 11.956 0 Td [(2 ;::: TheclaimisthatthissequencedenesaHamiltonianpathon)]TJ/F34 7.9701 Tf 330.135 -1.793 Td [(m R Thissequenceofelementsin Z ,whichisidentiedwithasequenceofmonomials in M I .Noticethatanythreeconsecutivetermsinthesequenceareoftheform f )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 k ;f )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 A )]TJ/F33 11.9552 Tf 10.929 0 Td [(k ;f )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 k +1or f )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 A )]TJ/F33 11.9552 Tf 10.93 0 Td [(k ;f )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 k +1 ;f )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 A )]TJ/F15 11.9552 Tf 10.93 0 Td [( k +1.Intherst case,wehavethat k + A )]TJ/F33 11.9552 Tf 11.427 0 Td [(k = A ,and A )]TJ/F33 11.9552 Tf 11.427 0 Td [(k + k +1= A +1andinthesecondcase, wehavethat A )]TJ/F33 11.9552 Tf 12.101 0 Td [(k + k +1= A +1,and k +1+ A )]TJ/F15 11.9552 Tf 12.102 0 Td [( k +1= A .ByProposition 6.4.2,thismeansthereisanedgebetweentheverticesrepresentedby f )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 k and f )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 A )]TJ/F33 11.9552 Tf 11.697 0 Td [(k aswellasthoserepresentedby f )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 A )]TJ/F33 11.9552 Tf 11.697 0 Td [(k and f )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 k +1,andsimilarly forthesecondcase.InordertohaveaHamiltonianpath,wemustassurethatno vertexisvisitedtwice.ByProposition6.4.1,wehavethat f isabijection,andas such,noelementsofthesequencearerepeated.Thus,wehaveourHamiltonianpath onthatsequenceofvertices.

PAGE 40

37 Example6.5. WecanusethisconstructiontogeneratetheHamiltonianpathin Example6.1,where = ; 3 ; 2.Oursequenceis1 ; 11 ; 2 ; 10 ; 3 ; 9 ; 4 ; 8 ;; 5 ; 7 ; 6which makesoursequenceoftriples ; 0 ; 0 ; ; 1 ; 1 ; ; 0 ; 0 ; ; 1 ; 1 ; ; 1 ; 0 ; ; 1 ; 1 ; ; 1 ; 0 ; ; 0 ; 1 ; ; 1 ; 0 ; ; 0 ; 1 ; ; 0 ; 1.Inmonomialform,thissequence is x;x 2 yz;x 2 ;xyz;y;yz;xy;x 2 z;x 2 y;xz;z ,whichisboldedbelow. Wenowhavefullydescribedthemonomialgraphsoffactorringswithspecic ideals.Namely,Artinianidealsoftheform h X 1 1 ;:::;X n n i .Wewillnowexamine thecasewhentheidealhasmixedmonomialsinadditiontoeachvariableraisedtoa power. Denition6.3. Let R = k [ X ],andlet I beanArtinianidealof R ,ifwehavea variabletoapower, x i i 2M I ,thenwedenetheupsilon-setof x i i as x i i = f 2M I x i i j g Thisisthesetofmonomialsin M I whicharedivisibleby x i i .Upsilonsetsgeneralize tomixedmonomialseasilyasfollows:if = Q n i =1 x i i ,then = S n i =1 x i i .

PAGE 41

38 Proposition6.5. Let R = k [ X ] I = h X 1 1 ;:::;X n n i .Thenif i 2M I ,and J = h 1 ;:::; m i ,letting R 1 = R= h I;J i ,yields j )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R 1 j = n Y i =1 i )-222(j [ j 2M I j j Proof. Itisusefultothinkof j )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R 1 j as jM h I;J i j ,since M h I;J i hasanicegeometric interpretation;apolytopewithintegercoordinates.Ifweconsiderjust M I ,wehave an n )]TJ/F15 11.9552 Tf 9.298 0 Td [(dimensionalboxwithonepointattheorigin.Let I j = h I; 1 ;:::; j i ,and consider I 1 .For I 1 ,wegetan n -dimensionalpolytopesimilartoExample5.9,which isthe3 )]TJ/F15 11.9552 Tf 9.299 0 Td [(dimensionalboxwithacornerremovedoppositetheorigin.Thenumberof pointsremovedisexactly j 1 j .Considering I 2 ,wehavethetotalnumberofpoints removedis j 1 [ 2 j .Itiscleartoseethatthisholdsthroughto I m = h I;J i ,which isthedesiredresult. Unfortunately,ndingthesizeoftheedgesetisnotsostraightforward.Wedosee that,aswiththevertexset,wehavesomeedgesbeingremovedwhentheverticesare removed,i.e.theedgesincidentwiththosevertices.However,inadditiontothose edgesbeingremoved,thenewmixedmonomialswillcreatenewedges.Onequick consequenceofthisisif R isasinProposition6.5andwehave R 1 = R= h I;J i and R 2 = R=I ,then,ingeneral,)]TJ/F34 7.9701 Tf 104.998 -1.793 Td [(m R 1 6 )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R 2 .Wecanstillcounttheedgesetin asimilarfashionasthevertexset,though,bydeningasimilarset.With I and J asbefore,let = f k ; l 2M h I;J i M h I;J i k 6 = l j k l g ,then isthe setofedgesaddeduponadditionof tothegeneratingsetof J .Asbefore,wetake theunionofthe 'stogetthetotalnumberofedgesadded.Allthatremainsisto subtractouttheedgesthatareremoved.Thusweseethatthenumberofedgesin )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R isgoingtobeafunctionintermsofthemixedmonomialsin J .Thisalgorithm doesnotlenditselftoaniceclosedformula,soonewillnotbegivenhere. RecallfromSection5that ^ I istheArtinianclosureofamonomialideal I .If I isnotArtinian,then I 6 = ^ I ,and,moreimportantly,if I isnotArtinian,thiscauses

PAGE 42

39 M I tobeinnite,andthus,themonomialgraphtobeinnite.Wewillusethis shortcomingofthemonomialgraphtoleadusintothenextsection. 7. Gr obnerBases Toexpandourstudyofringsusinggraphsdenedonzerodivisors,wewillneed tobefamiliarwithGrobnerbases.Manyofthepertinenttheoremsanddenitions willbegiveninthissection,andthereaderisreferredto[5]forfurtherreading.We beginwithafewterms,thenwewilldeneGrobnerbases.Wewillproceedwiththe generalizeddivisionalgorithmin R = k [ X 1 ;:::;X n ]where k isaeldofcharacteristic 0asbefore.ThisgeneralizedalgorithmwillallowustoconstructGrobnerbases.In previoussections,wehaveusedcapitalletterstodenotethevariables,andlower caseletterstodenotethecosetrepresentatives.Inthissection,wewillfollowthe conventionsusedin7,whichuseslowercaselettersforallvariables.Sincewearenot goingtobedealingwithfactorringsforthemajorityofthissection,therewillbeno confusion. For f 2 k [ X ],wewillsaythatLT f istheleadingtermof f withrespectto axedmonomialordering.If f X = P 2 A a X where A Z n 0 A niteand a 2 k;a 6 =0,thenmultideg f =max .Again,thismaxistakenwithrespect toaxedmonomialordering. Given I R ,wesaythat h LT I i istheidealgeneratedbytheleadingtermsof thepolynomialsin I Denition7.1. Let R = k [ x 1 ;:::;x n ]and I beanyidealof R .Withaxedmonomial ordering,anitesubset, G = f g 1 ;:::;g n g ,ofanyideal, I issaidtobeaGrobner basisof I if h LT g 1 ;:::; LT g n i = h LT I i InordertondaGrobnerbasisofanideal,wemustusetheBuchbergeralgorithm. Todothis,werstneedtounderstandthedivisionalgorithminmultiplevariables. Ourgoalinthisgeneralizedalgorithmistotakeapolynomial f 2 R = k [ x 1 ;:::;x n ], andasetofpolynomials f f 1 ; ;f n g in R ,andwrite f = a 1 f 1 + + a n f n + r with

PAGE 43

40 a i ;r 2 R .Thealgorithmwillfollowthepatternofthedivisionalgorithminone variableinthesensethatwewillcanceltheleadingtermof f bysomemonomial f 0 andthensubtract.Sincewehavemorethanonevariable,itisclearthatxing themonomialorderingisimperative.Wewillgivetwoexamples.Itisassumed throughoutthatthemonomialorderingbeingusedislexicographicwith x 1 >x 2 > >x n Example7.1. Let R = Q [ x;y ], f = xy 2 +1,and F = f f 1 ;f 2 g = f xy +1 ;y +1 g Wewillwrite f = a 1 f 1 + a 2 f 2 + r where r istheremaindersuchthat r =0or r is alinearcombinationofmonomialsfrom R suchthatLT f i LT r forall i .Weuse thefollowingsetup: a 1 : a 2 : xy +1 xy 2 +1 y +1 Here,theleadingtermsof f 1 and f 2 bothdividetheleadingtermof f ,sowewill use f 1 fortherststep.Thus,wehave: a 1 : y a 2 : xy +1 xy 2 +1 y +1 xy 2 + y )]TJ/F33 11.9552 Tf 9.299 0 Td [(y +1 Nowwerepeatthisprocesswiththenewpolynomial, )]TJ/F33 11.9552 Tf 9.299 0 Td [(y +1.Wewilluse f 2 this timesinceLT f 2 divides y ,andLT f 1 doesnot.Thisgivesus:

PAGE 44

41 a 1 : y a 2 : )]TJ/F15 11.9552 Tf 9.298 0 Td [(1 xy +1 xy 2 +1 y +1 xy 2 + y )]TJ/F33 11.9552 Tf 9.299 0 Td [(y +1 )]TJ/F33 11.9552 Tf 9.298 0 Td [(y )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 2 Nowweseethattheleadingtermsof f 1 and f 2 donotdivide2,so2istheremainder weseek.Thus, xy 2 +1= y xy +1+ )]TJ/F15 11.9552 Tf 9.299 0 Td [(1 y +1+2. Inthefollowingexample,wewillencounteramorecomplicatedremainder.Inthis example,wewillhaveanintermediatestepinwhichtheleadingtermsofthedivisors donotdividetheleadingtermofthedividend,butdodivideanotherterminthe dividend.Wewillseewhathappensinthiscase. Example7.2. Let R = Q [ x;y ], f = x 2 y + xy 2 + y 2 ,and F = f f 1 ;f 2 g = f xy )]TJ/F15 11.9552 Tf 9.384 0 Td [(1 ;y 2 )]TJ/F15 11.9552 Tf 9.384 0 Td [(1 g Wedonotencounteranythingunusualuntilafterthesecondstep,sowewillstart there: a 1 : x + yr a 2 :1 xy )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 x 2 y + xy 2 + y 2 y 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 x 2 y )]TJ/F33 11.9552 Tf 11.955 0 Td [(x xy 2 + x + y 2 xy 2 )]TJ/F33 11.9552 Tf 11.955 0 Td [(y Weseebelowthattheleadingtermsofthedivisorsdonotdividetheleadingterm ofthedividend,sowecreateanewcolumnfortheremainderand'eject'theleading termintoit.Wewriteitasfollows:

PAGE 45

42 a 1 : x + yr a 2 :1 xy )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 x 2 y + xy 2 + y 2 y 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 x 2 y )]TJ/F33 11.9552 Tf 11.955 0 Td [(x xy 2 + x + y 2 xy 2 )]TJ/F33 11.9552 Tf 11.955 0 Td [(y x + y 2 + y x Wecontinuethedivisioninthismanner,andweachieve: a 1 : x + yr a 2 :1 xy )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 x 2 y + xy 2 + y 2 y 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 x 2 y )]TJ/F33 11.9552 Tf 11.955 0 Td [(x xy 2 + x + y 2 xy 2 )]TJ/F33 11.9552 Tf 11.955 0 Td [(y x + y 2 + y x y 2 + y y 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 y +1 x + y 1 x + y +1 0 Thus,theremainderis x + y +1,andweobtain x 2 y + xy 2 + y 2 = x + y xy )]TJ/F15 11.9552 Tf 11.956 0 Td [(1+1 y 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ x + y +1 .

PAGE 46

43 Thisexampleillustratescompletelythetechniqueofthegeneralizeddivisionalgorithm.Theorem3ofchapter2of[5]formallystatesandprovesthegeneralizeddivisionalgorithm.Forourpurposes,weneedonlytohaveaworkingunderstandingofthealgorithm.Fornotationpurposes,theaboveexampleiswrittenas x 2 y + xy 2 + y 2 F = x + y +1.Thatis,forasetofpolynomials F ,ifwedividea polynomial f by F ,andgetaremainderof r ,thenwesay f F = r WecontinuenowwiththeconstructionofGrobnerbasesusingBuchberger'salgorithm. Denition7.2. Let f;g 2 k [ x 1 ;:::;x n ]benonzeropolynomials. Ifmultideg f = andmultideg g = ,thenlet = 1 ;:::; n ,where i = max i ; i forall i .Wecall x theleastcommonmultipleofLT f and LT g ,written x =LCMLT f ,LT g TheS-polynomialof f and g is S f;g = x LT f f )]TJ/F33 11.9552 Tf 22.126 8.088 Td [(x LT g g Example7.3. Let R = Q [ x;y;z ], f = x 2 y 3 z )]TJ/F33 11.9552 Tf 12.462 0 Td [(xy 4 z 2 +3 y 2 )]TJ/F15 11.9552 Tf 12.463 0 Td [(2 z g = x 4 z 2 )]TJ/F33 11.9552 Tf 12.463 0 Td [(y 2 z Then = ; 3 ; 2and S f;g = x 4 y 3 z 2 x 2 y 3 z f )]TJ/F33 11.9552 Tf 13.15 8.088 Td [(x 4 y 3 z 2 x 4 z 2 g = )]TJ/F33 11.9552 Tf 9.298 0 Td [(x 3 y 4 z 3 +3 x 2 y 2 z )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 x 2 z 2 )]TJ/F33 11.9552 Tf 11.955 0 Td [(y 5 z Theorem7.1. Buchberger'sCriterion Let I beapolynomialideal.Thena basis G = f g 1 ;:::;g n g for I isaGrobnerbasisifandonlyifforallpairs i 6 = j S g i ;g j G =0 Proof. Theorem6ofchapter2,section6in[5]. WenowseewhatittakestobeaGrobnerbasis,andthefollowingtheorem,also duetoBuchberger,ishowwewillconstructthebasis.Wewilldoanexamplerst, thenstatethealgorithmformallyusingpsuedocode.

PAGE 47

44 Example7.4. Let R = Q [ x;y;z ],andlet I = h f 1 ;f 2 ;f 3 ;f 4 i = h x 2 yz + xy 2 + yz;x 2 y;y 2 ;yz i .WebegintocalculatetheGrobnerbasisbyrstcalculatingallthe pairwiseleastcommonmultiplesofthegenerators. LCMLT f 1 ;f 2 = x 2 yz LCMLT f 1 ;f 3 = x 2 y 2 z LCMLT f 1 ;f 4 = x 2 yz LCMLT f 2 ;f 3 = x 2 y 2 LCMLT f 2 ;f 4 = x 2 yz LCMLT f 3 ;f 4 = y 2 z NowwemustcalculatethepairwiseS-polynomials. S f 1 ;f 2 = x 2 yz x 2 yz f 1 )]TJ/F34 7.9701 Tf 13.15 5.256 Td [(x 2 yz x y 2 x 2 y = f 2 + f 4 S f 1 ;f 3 = x 2 y 2 z x 2 yz f 1 )]TJ/F34 7.9701 Tf 13.15 5.256 Td [(x 2 y 2 z y 2 y 2 = xy 3 + y 2 z = f 3 xy + f 4 y S f 1 ;f 4 = x 2 yz x 2 yz f 1 )]TJ/F34 7.9701 Tf 13.15 5.256 Td [(x 2 yz yz yz = f 2 + f 4 S f 2 ;f 3 = x 2 y 2 x 2 y x 2 y )]TJ/F34 7.9701 Tf 13.15 5.256 Td [(x 2 y 2 y 2 y 2 =0 S f 2 ;f 4 = x 2 yz x 2 y x 2 y )]TJ/F34 7.9701 Tf 13.151 5.255 Td [(x 2 yz yz yz =0 S f 3 ;f 4 = y 2 z y 2 y 2 )]TJ/F34 7.9701 Tf 13.151 5.256 Td [(y 2 z yz yz =0 InBuchberger'salgorithm,itissucienttoshowthat,foreverytermineachnonzero S-polynomial,thereisageneratoroftheidealsuchthattheleadingtermofthat generatordividesit.ItisclearherethatalloftheS-polynomialssatisfythiscriterion. Thistellsusthatthegeneratingsetgivenfor I isalreadyaGrobnerbasis.Ifitwere thecasethattherewasanS-polynomialwhichhadatermthatwasnotdivisibleby thegeneratingsetof I ,thenwewouldtaketheremainderfromthatdivision,add ittothegeneratingset,andrepeatthewholeprocessoveragain.Thisexamplewas chosenforcomputationalsimplicity. Theorem7.2. Buchberger'sAlgorithm Let I = h f 1 ;:::;f s i6 = h 0 i beapolynomialideal.ThenaGrobnerbasisfor I canbeconstructedinanitenumberofsteps bythefollowingalgorithm:

PAGE 48

45 Input: F = f f 1 ;:::;f s g Output:aGrobnerbasis G = f g 1 ;:::;g t g for I ,with F G G := F REPEAT G 0 := G FOReachpair f p;q g p 6 = q in G 0 DO S := S p;q G 0 IF S 6 =0 THEN G := G [f S g UNTIL G = G 0 Proof. Theorem2ofchapter2,section7in[5]. Denition7.3. AminimalGrobnerbasisforapolynomialideal I isaGrobnerbasis for I suchthatalltermsofthepolynomialhavecoecient1andforall p 2 G ,LT p 62h LT G )-222(f p g i Denition7.4. AreducedGrobnerbasisforapolynomialideal I ,isaGrobnerbasis G for I suchthatalltermsofthepolynomialhavecoecient1andforall p 2 G ,no termin p isanelementof h LT G )-222(f p g i Bythesedenitions,weseethattheGrobnerbasisgivenintheexampleisnot minimal.Itiseasytosee,however,thatifaGrobnerbasisisnotreducedifitis reduced,itisclearlyminimal,onesimplyhastothrowouttheoendinggenerators, andareducedGrobnerbasiswillremain.Thus,theminimalGrobnerbasisfor Example7.4is f x 2 y;y 2 ;yz g .TheadvantagehereisthatthereducedGrobnerbasis isunique. Wecannowprovesomesimple,buthelpfulpropositions. Proposition7.1. Let R = k [ x 1 ;:::;x n ] andsuppose I = h g 1 ;:::;g t i isamonomial idealof R ,then G = f g 1 ;:::;g t g isaGrobnerbasisof I .

PAGE 49

46 Proof. Recallthat G isaGrobnerbasisifandonlyif S g i ;g j G =0forall i 6 = j where S = LCM g i ;g j LT g i g i )]TJ/F31 7.9701 Tf 12.998 6.083 Td [(LCM g i ;g j LT g j g j .Notice,though,thatsince g i and g j aremonomial, LT g i = g i ,andthus, S g i ;g j = LCM g i ;g j LT g i g i )]TJ/F15 11.9552 Tf 13.151 8.088 Td [(LCM g i ;g j LT g j g j =LCM g i ;g j )]TJ/F15 11.9552 Tf 11.956 0 Td [(LCM g i ;g j =0 Therefore, S g i ;g j G =0forall i 6 = j Corollary7.1. Let R = k [ x 1 ;:::;x n ] andsuppose I = h g 1 ;:::;g t i isamonomial idealof R ,if G = f g 1 ;:::;g n g isanantichain,then G isareducedGrobnerbasisof I Proof. ToobtainareducedGrobnerbasisofamonomialideal,onehastothrowout anygeneratorsthataredivisiblebyanyothergenerators.Sincenotwomonomials divideeachotherinanantichain,weclearlyhaveareducedGrobnerbasisof I Proposition7.2. Suppose I = h X 1 1 ;:::;X n n i and J = h X 1 1 ;:::;X n n ; 1 ;::: m i where i aremonomialsin k [ X 1 ;:::;X n ] .Ifforevery j ,thereexistsan X k k which dividesit,then k [ X 1 ;:::;X n ] =I = k [ X 1 ;:::;X n ] =J Proof. Both I and J areGrobnerbases,but J isnotreduced.ApplytheGrobner basisreductionalgorithmto J andthereducedGrobnerbasisis I 8. Gr obnerAnnihilatorGraph Sofarwehaveseenthezerodivisorgraph,annihilatorgraph,andthemonomial annihilatorgraph;wewillnowproceedtoamoregeneralversionofthemonomial annihilatorgraph,whichwewillcalltheGrobnerAnnihilatorGraph. Denition8.1. Let R = k [ X ]and I beanidealin R andxamonomialtermorder. TheGrobnerAnnihilatorGraphof R=I ,denoted)]TJ/F34 7.9701 Tf 59.184 -1.793 Td [(g R=I ,isdenedbyrsttaking thereducedGrobnerbasisof I ,whichwewillcall I g .Thatis, I g = I ,but I g hasa reducedGrobnerbasisforageneratingset.Wethentakethemonomialannihilator

PAGE 50

47 graphassociatedwiththeArtinianclosureoftheleadingtermidealof I g .Wewill callthisideal ~ I ,which,symbolically,is h LT I g i .Thatis,)]TJ/F34 7.9701 Tf 60.057 -1.793 Td [(g R=I =)]TJ/F34 7.9701 Tf 27.613 -1.793 Td [(m R= ~ I Remark 8.1 Noticethatifadierenttermorderischosen,theresultantGrobner graphwillbedierent,sotheGrobnerAnnihilatorGraphisdependentontheterm order.Alltheresultsherewillbevialexicographictermordering. Remark 8.2 AllGrobnerbasiscalculationswereperformedeitherinMaple10,orin CoCoA,andassuch,thedetailsareomitted.Also,lexicographictermorderingis usedineveryexample. Example8.1. Let R = Q [ X;Y ] = h X 3 )]TJ/F15 11.9552 Tf 15.59 0 Td [(3 XY;X 2 Y )]TJ/F15 11.9552 Tf 15.59 0 Td [(2 Y 2 + X i .Here, I g = h Y 6 )]TJ/F15 11.9552 Tf 15.438 0 Td [(3 Y 3 ;X + Y 5 )]TJ/F15 11.9552 Tf 15.438 0 Td [(2 Y 2 i ,andthus, ~ I = h X;Y 6 i .Therefore, )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(g R=I =)]TJ/F34 7.9701 Tf 27.612 -1.793 Td [(m Q [ X;Y ] = h X;Y 6 i =)]TJ/F34 7.9701 Tf 27.613 -1.793 Td [(m Q [ Y ] = h Y 6 i whichis Example8.2. Let R = Q [ X;Y;Z ] = h X 4 )]TJ/F33 11.9552 Tf 12.861 0 Td [(Y 2 Z;XZ )]TJ/F33 11.9552 Tf 12.862 0 Td [(Y;X )]TJ/F33 11.9552 Tf 12.861 0 Td [(XZ 3 i .Here, I g = h)]TJ/F33 11.9552 Tf 13.948 0 Td [(XZ 10 + Z; )]TJ/F33 11.9552 Tf 9.299 0 Td [(XZ + Y;X )]TJ/F33 11.9552 Tf 10.385 0 Td [(XZ 3 i .Weseethat h LT I g i = h)]TJ/F33 11.9552 Tf 13.948 0 Td [(XZ 10 ; )]TJ/F33 11.9552 Tf 9.299 0 Td [(XZ; )]TJ/F33 11.9552 Tf 9.298 0 Td [(XZ 3 i = h XZ i .WehavethatLCMLT I g = XZ ,andconsequently, ~ I = h X 2 ;Z 2 ;XZ i Therefore,ourGrobnerannihilatorgraphis

PAGE 51

48 Lemma8.1. Suppose R = k [ X 1 ;:::;X n ] and I isanidealof R .Then )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(g R=I containsavertexofdegree1ifandonlyif n =1 Proof. If n =1,then R= ~ I = k [ X 1 ] = h X 1 1 i and x 1 ;x 1 )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 1 2M I .Thevertex[ x 1 ]is adjacentonlytothevertex[ x 1 )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 1 ],therefore,wehaveavertexwithdegree1. Suppose ~ I = h X 1 1 ;:::;X n n ; 1 ;:::; m i .Wemustshowthat)]TJ/F34 7.9701 Tf 131.915 -1.793 Td [(g R=I hasno vertexofdegree1.Ifweconsiderthegenerator X 1 1 ,wehavetwooptions: X 1 j i forsome i .Let i = X 1 0 X 1 i forall i In, f x 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 1 ; 0 g Ann x 1 ,therefore,deg[ x 1 ] > 1.Therefore,allmonomials divisibleby x 1 willrepresentverticeswithdegreegreaterthan1.Thisargumentis symmetricinthechoiceofvariable. In, f x 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 1 ;x 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 1 x n g Ann x 1 .Asubcaseofwemustconsiderisif j = X 1 X n forsome j .Ifthishappens,then x 1 )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 1 x n 62 Ann x 1 byvirtueofitbeing 0already.Wewouldhave,however, f x 1 )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 1 ;x n g Ann x 1 .Thisresultisalso symmetricinthechoiceofvariable,thuswehavethedesiredcontradictionsand n is necessarily1. Beforeournextsetoftheorems,wemustdeneagraphwewillcall H n ,where n 2 Z > 0 Wehavethefollowing4stepconstructionalgorithmfor H n : Draw K d n +1 2 e Labelthevertices v 1 ;:::;v d n +1 2 e Draw n )-222(d n +1 2 e newverticesandlabelthem v 1 ;:::;v n d n +1 2 e Drawedgesbetween v k and v 1 ;:::;v k for1 k n )-222(d n +1 2 e Example8.3. Withtheaboveconstruction, H 8 and H 9 looklike

PAGE 52

49 Notethat H n canbeconstructedusingtheHavel-Hakimialgorithmonthedegree sequence1 ; 2 ; 3 ;:::; b n 2 c)]TJ/F15 11.9552 Tf 14.747 0 Td [(1 ; b n 2 c ; b n 2 c ; b n 2 c +1 ;:::;n )]TJ/F15 11.9552 Tf 9.366 0 Td [(1,asfoundin[7],[11].TheHavelHakimialgorithmconstructsasimplegraphbysuccessivelyconnectingthevertexof highestdegreetotheremainingverticesofhighestdegrees,reorderingremaining verticesbydegree,andrepeatingtheprocess.Wedened H n withthealgorithmfor easieruseincomingproofs.Noticethatdeg v k = n )]TJ/F33 11.9552 Tf 11.955 0 Td [(k anddeg v k = k Proposition8.1. H n hasaHamiltonianpath. Proof. Wewillexplicitlyconstructthepath.Noticethatdeg v 1 =1and v 1 is adjacentonlyto v 1 aspertheconstruction.Thus,inourpath,wemustbeginwith theedge v 1 v 1 .Sincedeg v 2 =2and v 2 isadjacentto v 1 ,thatforces v 1 v 2 tobeour secondedge.Theonlyothervertexadjacentto v 2 is v 2 ,soourthirdedgeisalso forced.Toseethatthispatternofforcededgescontinues,welookatthefourthedge. Sincedeg v 3 =3,andtheedge v 1 v 3 isdisallowedsince v 1 hasalreadybeenvisited, thatleavesuswithonly2useableedges,namely v 2 v 3 forgettingto v 3 and v 3 v 3 for leaving v 3 .Inthecasewhere n isodd,thiswillclearlycontinuetobethecaseallthe wayto v d n +1 2 e ,wherethepathwillend.Thenalpath,givenintermsofthevertices, is v 1 ;v 1 ;v 2 ;v 2 ;:::;v d n +1 2 e .Inthecasewhere n iseven,wecontinuesimilarly,butwe havethenal3verticesinthepathare v n 2 )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 ;v n 2 +1 ;v n 2 Example8.4. TheHamiltonianpathsconstructedinProposition8.1areshownhere for H 8 and H 9 .

PAGE 53

50 Proposition8.2. H n isuniquelydenedbyitsdegreesequence. Proof. Recallrstthatanygraphwithlessthan5verticesisuniquelydenedbyits degreesequence[9].Ifagraphhasthisproperty,wewillsimplysayitisuniquely dened.Also,ifwehaveagraphthatisuniquelydenedandweaddeitheravertex adjacenttoeverything,asocalleduniversalpoint,theuniquedenitionisunchanged. Furthermore,ifweaddavertexofdegree0,theuniquedenitionisstillunchanged. Nowconsider H 2 .Thisgraphhaslessthan5vertices,soitisuniquelydened, andifweaddauniversalvertextoit,ournewgraphstillis;callthisgraph H 2 .Now addavertexofdegree0to H 2 andthenmakeitadjacenttotheuniversalvertex.A moment'sconsiderationtellsusthatthisstilldoesnotaecttheuniquedenition. Wecanseethatthisnewgraphis H 4 .Since j H 4 j < 5,westillhaveuniquedenition, aswehadalreadyconcluded.Theevolutionfrom H 2 to H 4 isshownhere. Nowassumethat H k isuniquelydened.Ifweperformthesameoperationon H k ofaddingtheuniversalvertex,etc,wewillarriveat H k +2 ,whichwillalsobeuniquely denedbytheargumentfrombefore.Thus,if n iseven,wehavebyinductionthat

PAGE 54

51 H n isuniquelydened.If n isodd,wesimplydothesameinduction,butbeginwith H 1 instead. Proposition8.3. Let R = k [ X 1 ] = h X 1 1 i ,then )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(m R = H )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 Proof. Wehavethat M I = f x 1 ;x 2 1 ;:::;x 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 1 g .Wehavethefollowingmap: : V )]TJ/F34 7.9701 Tf 11.867 -1.793 Td [(g R V H 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 [ x 1 )]TJ/F34 7.9701 Tf 6.586 0 Td [(k 1 ]= 8 < : v k ;k d 1 2 e ; v k ; else Themap isclearlyabijectionsoitremainstoshowthatitpreservesadjacency. Toseethisis,wewillverifythatdeg[ x 1 )]TJ/F34 7.9701 Tf 6.586 0 Td [(k 1 ]=deg [ x 1 )]TJ/F34 7.9701 Tf 6.587 0 Td [(k 1 ],andfromthere,the edgeisomorphismwillbeobvious.Noticedeg[ x 1 )]TJ/F34 7.9701 Tf 6.587 0 Td [(k 1 ]= 1 )]TJ/F33 11.9552 Tf 12.045 0 Td [(k for1 k 1 )]TJ/F15 11.9552 Tf 12.045 0 Td [(1. Also,noticedeg v k = 1 )]TJ/F33 11.9552 Tf 12.221 0 Td [(k ,anddeg v k = 1 )]TJ/F33 11.9552 Tf 12.221 0 Td [(k for1 k 1 )]TJ/F33 11.9552 Tf 12.221 0 Td [(k .Since H n isuniquelydenedbyit'sdegreesequence,and)]TJ/F34 7.9701 Tf 251.795 -1.793 Td [(m R hasthesamedegreesequence as H 1 )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 bythemap, ,thenwehavethat)]TJ/F34 7.9701 Tf 110.717 -1.793 Td [(m R = H 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 Theorem8.1. Givenapolynomialring R = k [ X ] andanideal I of R )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(g R=I = H m ifand onlyif R=I isaprincipalidealdomain. If )]TJ/F34 7.9701 Tf 7.315 -1.794 Td [(g R=I = H s )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ,then h LT I i = h X s 1 i Proof. If R=I isaPID,andapolynomialring,thenitisnecessarilyoftheform k [ X 1 ] =I forsomeideal I .Thatis,apolynomialringisaPIDifandonlyifit containsonlyonevariable[12],Theorem4.5.6.SinceitisaPID, I = h p X 1 i forsomepolynomial p X 1 2 R .Then ~ I = h LT p X 1 i = h X s 1 i forsome s Thus,)]TJ/F34 7.9701 Tf 40.221 -1.793 Td [(g R =)]TJ/F34 7.9701 Tf 27.613 -1.793 Td [(m k [ X 1 ] = h X s 1 i whichisexactly H s )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 byProposition8.3. Conversely,suppose)]TJ/F34 7.9701 Tf 113.041 -1.793 Td [(g R=I = H s )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ,thenbyLemma8.1,wehavethat R mustbe k [ X 1 ],since H s )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 hasavertexofdegree1.Since k [ X 1 ]isaPID,we havethedesiredresult.

PAGE 55

52 From1,wehavethat R=I = k [ X 1 ] = h p X 1 i .Thus,LT p X 1 is X 1 raised apower.Bytheconstructionof H s ,thatpowerisnecessarily s +1. Proposition8.4. Let I beanidealof R = k [ X ] ,andthegeneratingsetof ~ I contains theset f X n 1 +1 ;:::;X n n +1 g .Then H n 1 ;:::;n n )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(g R=I ,where H n 1 ;:::;n n bethe disconnectedgraphwith n components H n 1 ;:::;H n n Proof. If X n i +1 i isageneratorof I ,thenusingthenotationfromtheproofofTheorem 5.2, X i M I .Thus,thesubgraphof)]TJ/F34 7.9701 Tf 138.094 -1.793 Td [(g R=I inducedon X i isexactly H n i ,by Proposition8.3.Therefore,eachgeneratorof I ofthatformhasadisjoint H graph associatedwithit.Theunionofthesegraphsyields H n 1 ;:::;n n asrequired. Noticethattheconverseistriviallyfalse.Inallcases, jM I j n ,thus,wehave H 1 ;:::; 1 | {z } ntimes asasubgraphof)]TJ/F34 7.9701 Tf 93.675 -1.793 Td [(g R=I forall R=I ,buttheset f X 2 1 ;:::;X 2 n ;:::;X 2 j M I j g isnotalwaysinthegeneratingsetof I Example8.5. Let R = k [ X;Y;Z ] = h X 3 ;Y 4 ;Z 3 ;XY 2 ;Y 2 Z;XZ i ,then M I = f x;x 2 ;y;y 2 ;y 3 ;z;z 2 ;xy;x 2 y;yz;yz 2 g and)]TJ/F34 7.9701 Tf 30.076 -1.793 Td [(g R is ByProposition8.4,weexpecttond H ; 3 ; 2 )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(g R ,whichwend:

PAGE 56

53 Denition8.2. Acliqueinagraphisacompletesubgraph,andthecliquenumber ofagraph G ,denotedby G ,isthesizeofthelargestcliquein G Example8.6. Byconstruction, H n = d n +1 2 e Theorem8.2. Suppose R = k [ X ] I = h X 1 1 ;:::;X n ; 1 ;:::; s i ,and 1 isthe greatestofthe i s.Let J betheidealgeneratedbyallthegeneratorsof I thatdonot containthevariable X 1 ,then d 1 2 e )]TJ/F34 7.9701 Tf 11.867 -1.793 Td [(g R=I d 1 2 e n Y i =2 j )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(g R=J j + d 1 2 e Proof. Since I = h X 1 1 ;:::;X n ; 1 ;:::; s i ,wehavebyProposition8.4that H 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 )]TJ/F34 7.9701 Tf 7.314 -1.794 Td [(g R=I ,andthus, )]TJ/F34 7.9701 Tf 11.866 -1.794 Td [(g R=I d 1 2 e byconstructionof H 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 .Toseetheupper bound,notethatwealreadyknowthelabelsoftheverticesintheminimumclique associatedwith H 1 )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 .Namely,theyare[ x b 1 2 c 1 ] ; [ x b 1 2 c +1 1 ] :::; [ x 1 )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 1 ]asdescribedin Proposition8.3.Noticethattheseverticesareadjacentbecausethepowerof x 1 is greaterthan i )]TJ/F15 11.9552 Tf 12.223 0 Td [(1whentheyaremultiplied.Inadditiontothesevertices,wehave verticeslabeledas[ x a 1 ]where d 1 2 e a 1 )]TJ/F15 11.9552 Tf 9.817 0 Td [(1and 2M I .Sincethesemonomials havethesamepowersof x 1 ,theywillalsobezerodivisors,andthuswillincreasethe sizeoftheclique.Togettheupperbound,noticethateachqualifying isavertex inthegraph)]TJ/F34 7.9701 Tf 76.583 -1.793 Td [(g R=J ,andthatweneedtoaddtheremaining d 1 2 e toaccountfor thepossibilitythat =1,whichwouldnotbeavertexin)]TJ/F34 7.9701 Tf 195.979 -1.793 Td [(g R=J

PAGE 57

54 Remark 8.3 Theboundsabovearesharpunderthefollowingconditions.Theleft handsideissharpifandonlyif n =1,andtherighthandsideissharpifandonly if s =0.Furthermore,if s =0,wecansimplifytherighthandsideas b 1 2 c Q n i =2 i If s 6 =0,wealreadyhavethemachinerytocalculatearenedupperbound.Ifwe consider J ,theninthering R=J ,wecanuseUpsilonsetsdenedinDenition6.3to determinetheupperboundsforanyvalueof s .Ingeneral,theupperboundwillnot besharp. Example8.7. Let R = k [ X;Y;Z ]andlet I = h X 3 ;Y 3 ;Z 3 ;XY;YZ;XZ i ,then M I = f x;x 2 ;y;y 2 ;z;z 2 g andconsequently,)]TJ/F34 7.9701 Tf 103.755 -1.793 Td [(g R=I = K 6 .Thecalculationofthe upperboundyields )]TJ/F34 7.9701 Tf 11.866 -1.793 Td [(g R=I 10since j )]TJ/F34 7.9701 Tf 7.314 -1.793 Td [(g k [ Y;Z ] = h Y 3 ;Z 3 ;YZ i j =4and d 3 2 e = 2. Denition8.3. Givenagraph G ,deneitscomplement, G c ,tobethegraphwhere V G = V G c ,andwheretwoverticesareadjacentin G c ifandonlyiftheyarenot adjacentin G Denition8.4. Wesaytheunion G oftwographs G 1 and G 2 isthegraphsuchthat V G = V G 1 [ V G 2 and E G = E G 1 [ E G 2 ,written G = G 1 [ G 2 ByRemark6.1,Grobnerannihilatorgraphsalwayscontainatleastoneuniversal vertex,sothecomplementwillnecessarilybedisconnected.Mosttimes,wewillnot needtoconsiderthesedisconnectedverticesinthecomplements.Assuch,wewill adopttheconventionofconsideringthecomplementoftheGrobnerannihilatorgraph tobetheunionoftwographs.Onegraphwillhavealltheedges,andasecondgraph willbetheemptygraphcontainingalltheverticesthatwereuniversalintheoriginal graph.Wewillcallthisemptygraph E Lemma8.2. H c n = H n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 [ E Proof. Webeginwiththedegreesequenceof H n ,1 ; 2 ; 3 ;:::; b n 2 c ; b n 2 c ; b n 2 c +1 ;:::;n )]TJ/F15 11.9552 Tf 9.464 0 Td [(1. Noticethatforanygraph G ,and v 2 V G ,if j G j = k anddeg v = d ,thenin G c ,the

PAGE 58

55 degreeof v is d )]TJ/F33 11.9552 Tf 11.184 0 Td [(k )]TJ/F15 11.9552 Tf 11.184 0 Td [(1.Weapplythistothedegreesequenceof H n togetthedegree sequenceof H c n .Beforereordering,wehave, n )]TJ/F15 11.9552 Tf 9.873 0 Td [(2 ;n )]TJ/F15 11.9552 Tf 9.873 0 Td [(3 ;n )]TJ/F15 11.9552 Tf 9.873 0 Td [(4 ;:::;n )-48(b n 2 c)]TJ/F15 11.9552 Tf 15.762 0 Td [(1 ;n )-48(b n 2 c)]TJ/F15 11.9552 Tf -416.813 -23.083 Td [(1 ;:::; 2 ; 1 ; 0.Uponreordering,wehave0 ; 1 ; 2 ; 3 ;:::;n )]TJ/F15 11.9552 Tf 10.307 0 Td [(1 )-84(b n 2 c ;n )]TJ/F15 11.9552 Tf 10.307 0 Td [(1 )-84(b n 2 c ;:::;n )]TJ/F15 11.9552 Tf 10.307 0 Td [(2. Wecansee,though,thatif n iseven, n )]TJ/F15 11.9552 Tf 10.886 0 Td [(1 )-133(b n 2 c = n )]TJ/F15 11.9552 Tf 10.885 0 Td [(1 )]TJ/F34 7.9701 Tf 12.08 4.707 Td [(n 2 = n 2 )]TJ/F15 11.9552 Tf 10.886 0 Td [(1= b n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 2 c .If n is odd,wehave n )]TJ/F15 11.9552 Tf 9.528 0 Td [(1 )-19(b n 2 c = n )]TJ/F15 11.9552 Tf 9.528 0 Td [(1 )]TJ/F34 7.9701 Tf 10.725 4.707 Td [(n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 2 = n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 2 = b n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 2 c .Thus,wehavethat n )]TJ/F15 11.9552 Tf 9.529 0 Td [(1 )-19(b n 2 c = b n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 2 c ,soournaldegreesequenceis0 ; 1 ; 2 ;:::; b n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 2 c ; b n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 2 c ; b n 2 c +1 ;:::;n )]TJ/F15 11.9552 Tf 11.335 0 Td [(2.But thisexactlythedegreesequencefor H n )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 withanadditionvertexofdegree0.Since H n isuniquelydenedbyitsdegreesequenceforall n ,wehavethedesiredresult. Denition8.5. If I isanidealof k [ X ],wesayapairedmonomialgenerator,PMG, isageneratorof I oftheform X i X j forsome i;j Proposition8.5. Consider R = k [ X ] and I anidealof R .If )]TJ/F34 7.9701 Tf 7.314 4.339 Td [(c g R=I hastwoor morecomponentswhichhaveatleastoneedgeeach,then ~ I hasatleast1PMG. Proof. Suppose)]TJ/F34 7.9701 Tf 52.278 4.339 Td [(c g R=I = G 1 [ G 2 [ E where G 1 and G 2 aredisjointcomponentswith atleastoneedgeeach,and E istheemptygraph.Thenwithoutlossofgenerality,one canreorderthevariablesin R=I suchthat G 1 containsthevertices[ x 1 ] ;:::; [ x k ], G 2 containsthevertices[ x k +1 ] ;:::; [ x l ],and E containsthevertices[ x l +1 ] ;:::; [ x n ].We havethattherearenoedgesbetween G 1 and G 2 in)]TJ/F34 7.9701 Tf 21.14 4.338 Td [(c g R=I ,so,in)]TJ/F34 7.9701 Tf 50.892 -1.794 Td [(g R=I ,allthe edgesmustbepresent.I.e.,in)]TJ/F34 7.9701 Tf 170.086 -1.793 Td [(g R=I ,thereexistsacompletebipartitesubgraph ontheverticesof G 1 and G 2 .Thus,wehavethat x i x j =0forall1 i k and k +1 j l whichconrmstheexistenceofPMGssincetheonlywayfor x i x j to be0isif X i X j isageneratorin I Proposition8.6. If R = k [ X 1 ;:::;X n ] ;n 3 I anidealof R ,and )]TJ/F34 7.9701 Tf 7.314 4.339 Td [(c g R=I = T [ E where T isatreegraphand E isempty.Then ~ I hasatleastonePMG,andif n =1 ~ I = h X a 1 i where 2 a 4 Proof. Weproceedbycontradiction.Suppose)]TJ/F34 7.9701 Tf 206.723 4.339 Td [(c g R=I = T [ E ,but ~ I hasnoPMGs. If R = k [ X 1 ;:::;X n ]and n 3,sincetherearenoPMGs,thevertices[ x 1 ] ; [ x 2 ]and

PAGE 59

56 [ x 3 ]willformatrianglein)]TJ/F34 7.9701 Tf 129.191 4.339 Td [(c g R=I ,whichcontradictshavingatreeasacomponent. If n =1,thenbyTheorem8.1,)]TJ/F34 7.9701 Tf 147.785 -1.793 Td [(g R=I = H m forsome m ,and H c m = H m )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 [ E by Lemma8.2.Weseebytheconstructionof H m thatitisatreefor1 n 3,thus, againbyTheorem8.1,ifwehaveatreewhen n =1,then ~ I = h X a 1 i for2 a 4as required. Proposition8.7. Given R = k [ X 1 ;:::;X n ] =I where I isanideal,if )]TJ/F34 7.9701 Tf 11.866 4.338 Td [(c g R = c and ~ I containsnoPMGs,then n c Proof. IftherearenoPMGsin ~ I ,thentherearenoedgesbetweenthepoints[ x 1 ] ;:::; [ x n ] in)]TJ/F34 7.9701 Tf 20.698 -1.793 Td [(g R .Consequently,in)]TJ/F34 7.9701 Tf 108.249 4.339 Td [(c g R ,thereisacompletegraphonthosevertices.Thus, wehavethat n )]TJ/F34 7.9701 Tf 11.867 4.338 Td [(c g R ,asrequired. 9. FurtherResearch Throughoutourdiscussion,wehaveworkedsolelywithcommutativerings,and morespecically,withpolynomialringsoveraeldwithcharacteristic0.Inthe followingexamples,wewillseethattheideasoftheannihilatorgraphasdenedin Section5canbeappliedtodierenttypesofrings. Werstlookatacommutativeringthatisnotapolynomialring.Inourexample, wewilltakeaclosedintervaloftherealline,anddivideitinto n +1intervalsofany length.I.e.,takeastrictlyincreasingsequenceof n +1realnumbers r 0 ;:::;r n ,and createthesubintervals,[ r i ;r i +1 ]of[ r 0 ;r n ]. Example9.1. Let i =[ r i ;r i +1 ]sotheinterval[ r 0 ;r n +1 ]= [ n i =0 i ,andlet R = f f : R R f hascompactsupportonexactlyone i g .Let f i representanelementof R supportedon i .Here, R isactuallyasubringofthewellknownringoffunctions withcompactsupportExample7,pp.225,[6].WeseethatAnn f i = f g k 2 R ki +1 g .Consequently,if n =7,wehavethefollowinggraph:

PAGE 60

57 Inanalexample,wewillexamineanoncommutativering.Inthecaseofa noncommutativering,wewilluseadirectedgraphtoindicatewhichdirectionthe multiplicationtookplace.Researchinthisareaisalreadytakingplaceforniterings, butwelookhereataninnitenoncommutativering[17]. Example9.2. Let R n bethegroupalgebra Q D 2 n andconsider R 3 .Elementsofthis ringareoftheform q 1 + q 2 r + q 3 r 2 + q 4 s + q 5 sr + q 6 sr 2 where q i 2 Q and r;s 2 D 6 .In ordertocalculateAnn x for x 2 R 3 ,weneedtocarryaboutthecalculation xy =0 where y isofthesameformas x .Thisprovestobeextremelytedious,sowewill carryoutjustoneofthecomputationshereforillustrativepurposes: Let x =1+ r + r 2 + s + sr + sr 2 andlet y = q 1 + q 2 r + q 3 r 2 + q 4 s + q 5 sr + q 6 sr 2 .Then xy = P 6 i =1 q i + r + r 2 + s + sr + sr 2 = P 6 i =1 q i x .If xy =0,then y = P 6 i =1 q i =0. Thus,wehave Ann x = f q 2 Q 6 j 6 X i =1 q i =0 g Thiswouldbejustonevertexinaninnitegraph,withdirectededgesgoingtoall theelementsof R 3 oftheaboveform,suchas1 )]TJ/F33 11.9552 Tf 11.955 0 Td [(r ,and r 2 + s )]TJ/F15 11.9552 Tf 11.956 0 Td [(2. Wewillendourexaminationoftheannihilatorgraphswithalistofquestionsthat couldbeaddressedinfutureresearch.

PAGE 61

58 Ifweletthecharacteristicoftheeld k benonzero,doesthisguaranteethat theannihilatorgraphwouldbeinnite?Ifnot,inwhatsituationswillitstill benite? Whatsortofrelationshipsexistbetweentheannihilatorgraph,theGrobner annihilatorgraph,andthezerodivisorgraphasdescribedin[2]? CanwegenerateclassesofnonisomorphicringswithisomorphicGrobnerannihilatorgraphsofarbitrarysize?Ifso,isthereanyoverlyingalgebraicstructure suchasagroupofrings,oraringofrings? Whatotherpropertiesof R canbeobtainedthroughanexaminationofthe graphtheoreticpropertiesof)]TJ/F34 7.9701 Tf 157.606 -1.794 Td [(g R ? Isthereanycorrespondencebetweensubgraphsof)]TJ/F34 7.9701 Tf 284.245 -1.793 Td [(g R andsubstructuresof R ? Canweprovethattheannihilatorgraphisuniquetoanyfactorring?

PAGE 62

59 ProgramusedinExample5.3 A;B;% Aisthealphavector,nisthenumberofvariables,Bisthebetavector k=0; fora=0:A forb=0:A forc=0:A ford=0:A S=[abcd]; C=A-B+S; g=0; ifC < =0 g=g+1; end ifC < =0 g=g+1; end ifC < =0 g=g+1; end ifC < =0 g=g+1; end ifg > 0 k=k+1; end end end end end f=k-1; f

PAGE 63

60 References [1]W.Adams,P.Loustaunau,AnIntroductiontoGrobnerBases ,AmericanMathematicalSociety,1994. [2]D.F.Anderson,P.S.Livingston, TheZero-Divisorgraphofacommutativering. J.Algebra ,1998,434-447. [3]Atiyah,MacDonald,IntroductiontoCommutativeAlgebra, Addison-WesleyPublishingCompany,1969. [4]I.Beck, Coloringofcommutativerings ,J.Algebra,1988,208-226. [5]D.Cox,J.Little,D.O'Shea,Ideals,Varieties,andAlgorithms ,Springer,2007. [6]D.Dummit,R.Foote,AbstractAlgebra ,JohnWileyandSons,Inc.,2004. [7]S.L.Hakimi, Ontherealizabilityofasetofintegersasdegreesoftheverticesofasimplegraph. J.SIAMAppliedMath,10,1962,496-506. [8]F.Harary,GraphTheory ,WestviewPress,1994. [9]F.Harary,E.M.Palmer,GraphicalEnumeration ,AcademicPress,1973. [10]N.Harseld,G.Ringel,PearlsinGraphTheory ,DoverPublications,Inc.,1994. [11]V.Havel, Aremarkontheexistenceofnitegraphs Czech, C asopisP e st.Math.80,1955, 477-480. [12]I.N.Herstein,AbstractAlgebra ,MacmillanPublishingCompany,1986. [13]E.Irigarary, CombinatorialKoszulHomology,Computations,andApplications ,2008, arXiv:0803.0421v1[math.AC]. [14]S.Mulay, Cyclesandsymmetriesofzerodivisors ,Comm.Algebra30,2002,3533-3558. [15]B.Sands, Countingantichainsinnitepartiallyorderedsets ,DiscreteMathematics,1981, 213-228. [16]S.Spiro,C.Wickham, Identifyingpropertiesofaringfromitszerodivisorgraph ,2007 arXiv:0801.0086v1[math.AC]. [17]Wu,Tongsuo, OndirectedZero-divisorgraphsofniterings. ,DiscreteMathematics, 2005,73-86.