graph connectivity and binomial edge ideals 2016 arindam banerjee学术.pdf

该【graph connectivity and binomial edge ideals 2016 arindam banerjee学术 】是由【探春文档】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【graph connectivity and binomial edge ideals 2016 arindam banerjee学术 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..PROCEEDINGSOFTHEAMERICANMATHEMATICALSOCIETYVolume145,Number2,February2017,Pages487–499http://dx./,2016GRAPHCONNECTIVITYANDBINOMIALEDGEIDEALSARINDAMBANERJEEANDLUISNU′NEZ-BETANCOURT?(CommunicatedbyIrenaPeeva)?cally,weshowifR/JGisaCohen-Macaulayring,-,westudytheHilbert-SamuelmultiplicityandtheHilbert-KunzmultiplicityofR/-Mumfordregularity,projectivedimension,andCohen-¨oberg’s[Fr¨o90]characterizationofedgeidealswithlinearminimalfreeresolutionsandHerzogandHibi’s[HH05]characterizationofCohen-,Hibi,Hreinsd′ottir,Kahle,andRauh[HHH+10],andbyOhtani[Oht11].Thisidealarisesnaturallyinthestudyofconditionalindependenceidealsthataresuitabletomodelrobustnessinthecontextofalgebraicstatistics[HHH+10].,theregularityofJGisboundedbelowbythelengthofthelargestinducedpathofGandabovebythenumberofverticesofG[MM13].Inaddition,Cohen-Macaulaynesshasbeencharacterizedforbinomialedgeidealsofchordalgraphsintermsofthemaximalcliquesoftheunderlyinggraph[EHH11].Furthermore,ithaspleteintersectionifandonlyifGisadisjointunionofpaths[EHH11,Rin13].Inthisarticlewestudytherelationshipofabinomialedgeidealandthecon-?cally,weinvestigateinteractionsbetweentoughnessandvertexconnectivityofagraphwithdimensionanddepthofR/,τ(G),ofagraphwas?rstintroducedbyChv′atal[Chv73]andservesasReceivedbytheeditorsJanuary23,2016and,inrevisedform,April4,?,05C40,,graphtoughness,vertexconnectivity,Cohen--1502282.?:35:;seernal-terms-of-use:..488ARINDAMBANERJEEANDLUISNU′NEZ-BETANCOURT?ameasureofconnectivityforagraph().ThisinvariantcanbeseenastheminimumratioofthecardinalityofasetofverticesthatmakeGdiscon-[BBS06].-suresofconnectivityrelateinthefollowingway:hightoughnessimplieshighvertexconnectivity().Our?rstmaintheoremgivesanecessaryconditiononthetoughnessofGforCohen-().LetGbeaconnectedgraphon[n]andJGthecorrespondingbinomialedgeidealinR=K[x1,...,xn,y1,...,yn].IfR/JGisCohen-Macaulay,theneitherτ(G)=?rstisarelationbetweenthetoughnessofGandthedimensionofR/JG().ThisrelationwasmotivatedfromthefactthatthedimensionofR/JGisgivenbythedi?erenceponentsintheinducedgraph,,thenGcannotbe2-vertex-connected().Pushingthisidea,weobtainoursecondmaintheorem,whichestablishesastrongerrelationbetweenthedepthofR/().LetGbeaconnectedgraphon[n]andJGthecorrespondingbinomialedgeidealinR=K[x1,...,xn,y1,...,yn].Supposepletegraphandthat,depth(R/JG)≤n?+2andpd(R/JG)≥n+?-Macaulay,thenthetoughnessis1andthevertex-,binatorialcriteria2toidentifygraphssuchthatR/JGisnotCohen-?nalsectionofthispaper,×?cally,[BV88];forinstance,theyareCohen--KunzandHilbert-Samuelmultiplicitiesforbinomialedgeidealsintermsofthecombinatoricsofthegraph().Asaconsequenceoftheseresults,theHilbert-KunzmultiplicityofR/,thevaluesofthemultiplicitiesdependonlyonthestructureofthegraphandnotonthecharacteristicofthecoe?cient?,-,werecallthede?nitionand?:35:;seernal-terms-of-use:..?nitionsandre-[Bol98][n]:={1,...,n}.GivenagraphGandasubsetofverticesS,c(S)denotestheponentsofG\?-vertex-connectedif<nandforeverysubsetSofverticessuchthat|S|<,theinducedgraphG\-connectivityofG,denotedbyκ(G),isde?nedasthemaximumintegersuchthatGis-vertex-?[BBS06]?([Chv73]).Wesaythataconnectedgraphist-toughifforeverysubsetS=?suchthatc(S)≥2,wehavet·c(S)≤|S|.hetoughnessofG,τ(G),asthemaximumvalueoftforwhichGist-,G,plete,then|S|τ(G)=min:c(S)≥(S):(1)pletegraph,thenτ(Kn)=∞andκ(G)=n?1.(2)IfKm,pletebipartitegraphwith2≤m≤n,thenτ(Km,n)=mnandκ(G)=m.(3)IfPnisthen-path,with3≤n,thenτ(Pn)=1andκ(G)=(4)isthen-cycle,with4≤n,)=1andκ(G)=2.(5)IfGisaHamiltoniangraph,thenτ(G)≥1andκ(G)≥-tough,witht>0,then|S|≥tforeverysubsetS?[n]suchthatc(S)≥,|S|≥t·c(s)c(S)foreverysetsuchthatc(S)≥,2t≥|S|isanecessaryconditiontohavec(S)≥<2tverticesareremoved,thenc(S)=1,soG\,Gisa2t-vertex-[x1,...,xn,y1,...,yn],apolynomialringin2nvariablesovera??[n].hebinomialedgeidealcorrespondingtoGbyJG=(xiyj?xjyi:{i,j}∈Gandi=j).[n].ThebinomialedgeidealcorrespondingtoGisJG=(xiyj?xjyi:i=j)=I2(X),x1...xnwhereX=.y1...ynDe?[n],andS?[n].LetG1,...,Gc(S)denotetheponentsofG\:35:;seernal-terms-of-use:..490ARINDAMBANERJEEANDLUISNU′NEZ-BETANCOURT? PS(G)={xi,yi},JG1,...,JGc(S)∈SItiswell-knownthatPS(G)isaprimeidealforeveryS?[n].Furthermore,([HHH+10,]).LetGbeagraphon[n],JG=PS(G).S?[n]([HHH+10,]).IfGisaconnectedgraphon[n],thenP?(G),weobtaindimR/JG=max{n?c(S)+|S|:S?[n]}becausedimR/PS(G)=n?c(S)+|S|[HHH+10,].IfGisconnectedandS[n]issuchthatc(S)=1,thenP?(G)?PS(G).Therefore,PS(G),??J(S)=?PS(G)?P?(G)c(S)≥2anddimR/JG=max{n+c(S)?|S|:c(S)≥2orS=?}.,-lishrelationsbetweengraphtoughnessanddi?erentaspectsrelatedtothedimen--[n],thefollowingareequivalent:(1)Gis1-tough;(2)dim(R/JG)=n+1andP?(G)istheonlyminimalprimeofdimensionn+-toughifandonlyifc(S)≤|S|foreverySsuchthatc(S)≥(G)=n+c(s)?|S|≤nforc(S)≥,.,weobtaincharacterizationefrom1-:35:;seernal-terms-of-use:..[n]-,thefollowingareequivalent:(1)R/JGisaCohen-Macaulayring;(2)R/JGisanequidimensionalring;(3)R/JGisadomain;(4),theequidimensionalityofR/[n]andJGthecorrespondingbino-(G)<,1?τ(G)n+≤dim(R/JG)n+(n?1)·(1?τ(G)).τ(G)(G)<1,,|S|τ(G)=min:c(S)≥2c(S),wehaveτ(G)≤|S|foreveryS[n]suchthatc(S)≥,c(S)τ(G)·c(S)≤|S|,andsoc(S)?|S|≤(1?τ(G))·c(S).Wenotethatc(S)≤n?1forS[n].Then,()c(S)?|S|≤(n?1)·(1?τ(G))foreverySsuchthatc(S)≥,max{n+c(S)?|S|:c(S)≥2}≤n+(n?1)·(1?τ(G))by().Sinceτ(G)<1,wehaveτ(G)≤1?(S)≤n??1Then,n+1≤n+(n?1)·(1?τ(G)).Hence,dim(R/JG)=max{n+c(S)?|S|:c(S)≥2orS=?}≤n+(n?1)·(1?τ(G)).|S|Ontheotherhand,thereexistsS[n]suchthatc(S)≥2andτ(G)=c(S)by,c(S)=1|S|,andso|S|1?τ(G)=c(S)?|S|.Since|S|≥1,τ(G)τ(G)wehave1?τ(G)≤c(S)?|S|.Therefore,τ(G)1?τ(G)n+≤n+c(S)?|S|≤dim(R/JG)τ(G)().Asaconsequenceoftheprevioustheorem,wehavethatthedimensionofR/:35:;seernal-terms-of-use:..492ARINDAMBANERJEEANDLUISNU′NEZ-BETANCOURT?[n]andJGthecorrespondingbino-,1≤τ(G).dim(R/JC)?n+1Inaddition,ifGisnot1-tough,thendim(R/JG)?1τ(G)≤.n?(R/JC)≥n+1,wehave1≤(R/JC)?n+12not1-tough,thenτ(G)<,itsu?cestoshowthestatementsforτ(G)<.,thefollowingresultshowsthatifR/JisCohen-Macaulay,then1≤τ(G).[n]andJGthecorrespondingbino-,pletegraphor1≤τ(G)<,a1-,τ(G)<,thendim(R/JG)=n+,1≤τ(G).2WenowstartwithpreparationresultsneededtoshowtheotherinequalityofTheoremA:ifR/JGisCohen-Macaulay,thenτ(G)≤[n]-vertex-connected