New College of Florida Brilliantly Unique; Uniquely Brilliant
<%BANNER%>

The Grobner Annihilator Graph of a Ring

MISSING IMAGE

Material Information

Title:
The Grobner Annihilator Graph of a Ring
Physical Description:
Book
Language:
English
Creator:
McGuire, Trevor
Publisher:
New College of Florida
Place of Publication:
Sarasota, Fla.
Creation Date:
2009
Publication Date:

Thesis/Dissertation Information

Degree:
Bachelor's ( B.A.)
Degree Grantor:
New College of Florida
Degree Divisions:
Natural Sciences
Degree Disciplines:
Mathematics
Committee Members:
Poimenidou, Eirini

Subjects

Subjects / Keywords:
Gr�bner Bases
Zero Divisor Graph
Annihilators
Genre:
Electronic Thesis or Dissertation
bibliography   ( marcgt )
theses   ( marcgt )
government publication (state, provincial, terriorial, dependent)   ( marcgt )

Notes

Abstract:
In recent years, graph theory has been used as a tool to study rings in the form of several different graphs, many of which are based on the zero divisor structure of the ring. We define here the annihilator graph of a ring to try to harness the best possible graphical representation of a ring. This paper lays the foundation for the theory of annihilator graphs and the extension of them to a more general form, the Gr�bner annihilator graph. We will study the relationships between the algebraic properties of a ring, and the graph theoretic properties of the Gr�bner annihilator graph of that ring.
Thesis:
Thesis (B.A.) -- New College of Florida, 2009
Electronic Access:
RESTRICTED TO NCF STUDENTS, STAFF, FACULTY, AND ON-CAMPUS USE
Bibliography:
Includes bibliographical references.
Source of Description:
This bibliographic record is available under the Creative Commons CC0 public domain dedication. The New College of Florida, as creator of this bibliographic record, has waived all rights to it worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
Local:
Faculty Sponsor: Poimenidou, Eirini
Statement of Responsibility:
by Trevor McGuire

Record Information

Source Institution:
New College of Florida
Holding Location:
New College of Florida
Rights Management:
Applicable rights reserved.
Classification:
local - S.T. 2009 M15
System ID:
NCFE004143:00001

MISSING IMAGE

Material Information

Title:
The Grobner Annihilator Graph of a Ring
Physical Description:
Book
Language:
English
Creator:
McGuire, Trevor
Publisher:
New College of Florida
Place of Publication:
Sarasota, Fla.
Creation Date:
2009
Publication Date:

Thesis/Dissertation Information

Degree:
Bachelor's ( B.A.)
Degree Grantor:
New College of Florida
Degree Divisions:
Natural Sciences
Degree Disciplines:
Mathematics
Committee Members:
Poimenidou, Eirini

Subjects

Subjects / Keywords:
Gr�bner Bases
Zero Divisor Graph
Annihilators
Genre:
Electronic Thesis or Dissertation
bibliography   ( marcgt )
theses   ( marcgt )
government publication (state, provincial, terriorial, dependent)   ( marcgt )

Notes

Abstract:
In recent years, graph theory has been used as a tool to study rings in the form of several different graphs, many of which are based on the zero divisor structure of the ring. We define here the annihilator graph of a ring to try to harness the best possible graphical representation of a ring. This paper lays the foundation for the theory of annihilator graphs and the extension of them to a more general form, the Gr�bner annihilator graph. We will study the relationships between the algebraic properties of a ring, and the graph theoretic properties of the Gr�bner annihilator graph of that ring.
Thesis:
Thesis (B.A.) -- New College of Florida, 2009
Electronic Access:
RESTRICTED TO NCF STUDENTS, STAFF, FACULTY, AND ON-CAMPUS USE
Bibliography:
Includes bibliographical references.
Source of Description:
This bibliographic record is available under the Creative Commons CC0 public domain dedication. The New College of Florida, as creator of this bibliographic record, has waived all rights to it worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
Local:
Faculty Sponsor: Poimenidou, Eirini
Statement of Responsibility:
by Trevor McGuire

Record Information

Source Institution:
New College of Florida
Holding Location:
New College of Florida
Rights Management:
Applicable rights reserved.
Classification:
local - S.T. 2009 M15
System ID:
NCFE004143:00001


This item is only available as the following downloads:


Full Text

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.


Facebook Twitter YouTube Regulations - Careers - Contact UsA-Z Index - Google+

New College of Florida  •  5800 Bay Shore Road  •  Sarasota, FL 34243  •  (941) 487-5000