Algebraic and combinatorial properties of ideals a

arXiv:0801.1478v1[math.AC]9Jan2008AlgebraicandcombinatorialpropertiesofidealsandalgebrasofuniformcluttersofTDIsystemsLuisA.DupontandRafaelH.Villarreal1DepartamentodeMatem´aticasCentrodeInvestigaci´onydeEstudiosAvanzadosdelIPNApartadoPostal14–74007000M´exicoCity,D.F.e-mail:[e-mail]clutter,i.e.,alltheedgesofChavethesamesize,andletAbetheincidencematrixofC.WedenotethecolumnvectorsofAbyv1,...,vq.ThevertexcoveringnumberofC,denotedbyα0(C),isthesmallestnumberofverticesinanyminimalvertexcoverofC.UndercertainconditionsweprovethatCisvertexcritical.IfCsatisfiesthemax-flowmin-cutproperty,weprovethatAdiagonalizesoverZtoanidentitymatrixandthatv1,...,vqisaHilbertbasis.ItisshownthatifChasaperfectmatchingsuchthatChasthepackingpropertyandα0(C)=2,thenAdiagonalizesoverZtoanidentitymatrix.IfAisabalancedmatrixweprovethatanyregulartriangulationoftheconegeneratedbyv1,...,vqisunimodular.Someexamplesarepresentedtoshowthatourresultsonlyholdforuniformclutters.Theseresultsarecloselyrelatedtocertainalgebraicproperties,suchasthenormalityortorsionfreeness,ofblowupalgebrasofedgeidealsandtofinitelygeneratedabeliangroups.TheyarealsorelatedtothetheoryofGr¨obnerbasesoftoricidealsandtoEhrhartrings.1IntroductionLetR=K[x1,...,xn]beapolynomialringoverafieldKandletIbeanidealofRofheightgminimallygeneratedbyafinitesetF={xv1,...,xvq}ofsquare-freemonomials.Asusualweusethenotationxa:=xa11···xann,wherea=(a1,...,an)∈Nn.Thesupportofxaisgivenbysupp(xa)={xi|ai0}.FortechnicalreasonsweshallassumethateachvariablexioccursinatleastonemonomialofF.02000MathematicsSubjectClassification.Primary13H10;Secondary13F20,13B22,52B20.1PartiallysupportedbyCONACyTgrant49251-FandSNI.1AclutterwithfinitevertexsetXisafamilyofsubsetsofX,callededges,noneofwhichisincludedinanother.ThesetofverticesandedgesofCaredenotedbyV(C)andE(C)respectively.Cluttersarespecialtypesofhypergraphs.Forathoroughstudyofcluttersandhypergraphsfromthepointofviewofcombinatorialoptimizationsee[5,17].WeassociatetotheidealIaclutterCbytakingthesetofindeterminatesX={x1,...,xn}asvertexsetandE={f1,...,fq}asedgeset,wherefkisthesupportofxvk.TheassignmentI7→Cgivesanaturalonetoonecorrespondencebetweenthefamilyofsquare-freemonomialidealsandthefamilyofclutters.TheidealIiscalledtheedgeidealofC.TostresstherelationshipbetweenIandCwewillusethenotationI=I(C).The{0,1}-vectorvkisthesocalledcharacteristicvectororincidencevectoroffk,i.e.,vk=Pxi∈fkei,whereeiistheithunitvector.LetAbetheincidencematrixofCwhosecolumnvectorsarev1,...,vq.ThesetcoveringpolyhedronofCisgivenby:Q(A)={x∈Rn|x≥0;xA≥1},where1=(1,...,1).AsubsetC⊂XiscalledaminimalvertexcoverofCif:(i)everyedgeofCcontainsatleastonevertexofC,and(ii)thereisnopropersubsetofCwiththefirstproperty.ThemapC7→Pxi∈CeigivesabijectionbetweentheminimalvertexcoversofCandtheintegralvectorsofQ(A).Apolyhedroniscalledanintegralpolyhedronifithasonlyintegralvertices.Aclutteriscalledd-uniformoruniformifallitsedgeshaveexactlydvertices.WebegininSection2byintroducingvariouscombinatorialpropertiesofclutter.Wethengiveasimplecombinatorialproofofthefollowingresultof[9]:Proposition2.2IfCisad-uniformclutterwhosesetcoveringpolyhedronQ(A)isintegral,thenthereareX1,...,XdmutuallydisjointminimalvertexcoversofCsuchthatX=∪di=1Xi.Inparticular|supp(xvi)∩Xk|=1foralli,k.Theoriginalproofofthisresultwasalgebraic.ItwasbasedonthefactthattheradicaloftheidealIR[It]canbeexpressedintermsoftheminimalprimesofI,whereR[It]istheReesalgebraofI(seeSection3).Example2.3showsthatthisresultfailsifwedroptheuniformityhypothesis.ForusebelowwedenotethesmallestnumberofverticesinanyminimalvertexcoverofCbyα0(C).TheclutterobtainedfromCbydeletingavertexxiandremovingalledgescontainingxiisdenotedbyC\{xi}.AsetofpairwisedisjointedgesofCiscalledindependentoramatchingandasetofindependentedgesofCwhoseunionisXiscalledaperfectmatching.Wethenprove:Proposition2.7LetCbead-uniformclutterwithaperfectmatchingsuchthatQ(A)isintegral.ThenCisvertexcritical,i.e.,α0(C\{xi})α0(C)foralli.2Asimpleexampleisshowntoseethatthisresultfailsfornonuniformclutterswithintegralsetcoveringpolyhedron(Remark2.8).InSection3weintroduceReesalgebras,Ehrhartrings,andedgesubrings.Certainalgebraicpropertiesofthesegradedalgebrassuchasthenormalityandtorsionfreenessarerelatedtocombinatorialoptimizationpropertiesofclutterssuchasthemax-flowmin-cutproperty(seeDefinition3.3)andtheintegralityofQ(A)[9,10].Thisrelationbetweenalgebraandcombinatoricswillbequiteusefulhere.InTheorems3.2,3.4,andProposition3.5wesummarizethealgebro-combinatorialfactsneededtoshowthemainresultofSection3:Theorem3.6IfCisauniformclutterwiththemax-flowmin-cutproperty,then(a)Δr(A)=1,wherer=rank(A).(b)NA=R+A∩Zn,whereA={v1,...,vq}.HereΔr(A)denotesthegreatestcommondivisorofallthenonzeror×rsub-determinantsofB,NAdenotesthesemigroupgeneratedbyA,andR+AdenotestheconegeneratedbyA.Condition(b)meansthatAisaHilbertbasisforR+A.AsaninterestingconsequenceweobtainthatifCisauniformclutterwiththemax-flowmin-cutproperty,thenAdiagonalizesoverZ—usingrowandcolumnoperations—toanidentitymatrix(seeCorollary3.8).InExample3.7weshowthat