On the independence complex of square grids

arXiv:math/0701890v2[math.CO]8Mar2007ONTHEINDEPENDENCECOMPLEXOFSQUAREGRIDSMIREILLEBOUSQUET-MLOU,SVANTELINUSSON,ANDERANNEVOAbstrat.Theenumerationofindependentsetsofregulargraphsisofinterestinstatistialmehanis,asitorrespondstothesolutionofhard-partilemodels.In2004,itwasonjeturedbyFendleyetal.thatforsomeretangulargrids,withtoriboundaryonditions,thealternatingnumberofindependentsetsisextremelysimple.Morepreisely,underaoprimalityonditiononthesidesoftheretangle,thenumberofindependentsetsofevenandoddardinalityalwaysdierby1.Inphysisterms,thismeanslookingatthehard-partilemodelonthesegridsatativity−1.ThisonjeturewasreentlyprovedbyJonsson.Hereweprodueotherfamiliesofgridgraphs,withopenorylindriboundaryonditions,forwhihsimilarpropertiesholdwithoutanysizerestrition:thenumberofindependentsetsofevenandoddardinalityalwaysdierby0,±1,or,intheylindriase,bysomepowerof2.Weshowthattheseresultsreetastrongerpropertyoftheindependeneomplexesofourgraphs.WedeterminethehomotopytypeoftheseomplexesusingForman’sdisreteMorsetheory.Wendthattheseomplexesareeitherontratible,orhomotopitoasphere,or,intheylindriase,toawedgeofspheres.Finally,weuseourenumerativeresultstodeterminethespetraofertaintransfermatriesdesribingthehard-partilemodelonourgraphsatativity−1.TheseresultsparallelertainonjeturesofFendleyetal.,provedbyJonssoninthetoriase.1.IntrodutionThehard-squaremodelisafamousopenprobleminstatistialmehanis.Inthismodel,someofthevertiesofanNbyNsquaregridareoupiedbyapartile,withtherestritionthattwoadjaentvertiesareneverbothoupied(Figure1).Ingraphtheoretiterms,anadmissibleongurationofpartilesisjustanindependentsetofthesquaregrid,thatis,asetofpairwisenon-adjaentverties.Thekeyquestionistoenumeratethesesetsbytheirsize,thatis,todeterminethefollowingpartitionfuntionatativityu:ZN(u)=XIu|I|,wherethesumrunsoverallindependentsetsofthegrid.Thisproblemishighlyunsolved:onedoesnotknowhowtoexpressZN(u),noreventhethermodynamilimitofthesequeneZN(u)(thatis,thelimitofZN(u)1/N2).ThemostnaturalspeializationofZN(u),obtainedforu=1,ountsindependentsetsoftheN×N-grid.Itisalsoextremelymysterious:neitherthesequeneZN(1),northelimitofZN(1)1/N2(theso-alledhard-squareonstant)areknown.WereferthereadertotheentryA006506intheOn-lineEnylopediaofIntegerSequenesformoredetails[10℄.Date:Mars7,2007.12MIREILLEBOUSQUET-MLOU,SVANTELINUSSON,ANDERANNEVONotethatthethermodynamilimitofZN(u)isknownifonereplaesthesquaregridbyatriangularoneatourdeforeahievedbyBaxterin1980[1℄.Figure1.Ahardpartileongurationoranindependentsetofthe7×7-grid.In2004,Fendley,ShoutensandvanEerten[3℄publishedaseriesofremarkableonjeturesonthepartitionfuntionofthehard-squaremodelspeializedatu=−1.Forinstane,theyobservedthatforanM×N-grid,takenwithtoriboundaryonditions,thepartitionfuntionatu=−1seemedtobeequalto1assoonasMandNwereoprime.Theyalsorelatedthisonjeturetoastrongerone,dealingwiththeeigenvaluesoftheassoiatedtransfermatries.TheseonjetureshavereentlybeenprovedinasophistiatedwaybyJonsson[8℄.Oneoftheaimsofthispaperistoprovethatsimilarresultshold,ingreatergenerality,forothersubgraphsofthesquarelattie,likethe(tilted)retanglesofFigure2(theywillbedenedpreiselyinSetion3).Forthesegraphs,weprovethatthepartitionfuntionatu=−1isalways0,1or−1.R(6,8)R(6,9)R(7,8)R(7,9)(0,0)Figure2.TheretangulargraphsR(M,N),denedinSetion3.Wethenshowthattheseresultsatuallyreetastrongerpropertyoftheinde-pendeneomplexofthesegraphs.TheindependentsetsofanygraphG,orderedbyinlusion,formasimpliialomplex,denotedbyΣ(G).SeeFigure3,wherethisom-plexisshownfora2×2-gridG.The(redued)Eulerharateristiofthisomplexis,bydenition:˜χG=XI∈Σ(G)(−1)|I|−1.Thequantity|I|−1isthedimensionoftheellI.TheabovesumisexatlytheoppositeofthepartitionfuntionZG(u)ofthehard-partilemodelonG,evaluatedatu=−1.Thisnumber,ZG(−1)=XI∈Σ(G)(−1)|I|=−˜χG,(1)willoftenbealledthealternatingnumberofindependentsets.ThesimpliityoftheEulerharateristiforertaingraphsGsuggeststhattheomplexΣ(G)ouldONTHEINDEPENDENCECOMPLEXOFSQUAREGRIDS3haveaverysimplehomotopytype(werefertoMunkres[9℄forthetopologialtermsinvolved).Weprovethatthisisindeedtheaseforvarioussubgraphsofthesquarelattie.Forinstane,fortheretanglesofFigure2,theindependeneomplexisalwayseitherontratible,orhomotopyequivalenttoasphere.OurresultsrelyontheonstrutionofertainMorsemathingsoftheomplexΣ(G).Roughlyspeaking,thesemathingsareparityreversinginvolutionsonΣ(G)havingertainadditionalinterestingproperties.4123{1}{2}{3}{4}{1,3}{2,4}∅˜R(3,3)˜R(5,5)Figure3.Twographs,andtheindependeneomplexofthetopone.ThisomplexhasreduedEulerharateristi1,andishomotopitoa0-dimensionalsphere(twopoints).ThepatientreaderanhekthatfortheSwissross˜R(5,5),thereduedEulerharateristiis−1.Theorrespondingomplexishomotopitoa3-dimensionalsphere.Letusnowdesribetheontentsofthispaper,andompareittoJonsson’sresults.InSetion2,werstreviewtheneededbakgroundofForman’sdisreteMorsetheory[4℄.WethendesribeageneralonstrutionofMorsemathingsfortheindependeneomplexofanygraph.Themathingsweonstrutareenodedbyamathingtree.InSetions3to5,weapplythisgeneralmahinerytodeterminethehomotopytypeoftheindependeneomplexofs