An introduction to the dimer model

arXiv:math/0310326v1[math.CO]20Oct2003AnintroductiontothedimermodelRichardKenyon∗February1,20081IntroductionAperfectmatchingofagraphisasubsetofedgeswhichcoverseveryvertexexactlyonce,thatis,foreveryvertexthereisexactlyoneedgeinthesetwiththatvertexasendpoint.Thedimermodelisthestudyofthesetofperfectmatchingsofa(possiblyinfinite)graph.Themostwell-knownexampleiswhenthegraphisZ2,forwhichperfectmatchingsareequivalent(viaasimpleduality)todominotilings,thatis,tilingsoftheplanewith2×1and1×2rectangles.Inthefirstthreesectionswestudydominotilingsoftheplaneandoffinitepolygonalregions,orequivalently,perfectmatchingsonZ2andsubgraphsofZ2.InthelasttwosectionswestudytheFK-percolationmodelandthedimermodelonamoregeneralfamilyofplanargraphs.2ThenumberofdominotilingsofachessboardAfamousresultofKasteleyn[8]andTemperleyandFisher[18]countsthenumberofdominotilingsofachessboard(oranyotherrectangularregion).InthissectionweexplainKaste-leyn’sproof.2.1CombinatoricsLetRbetheregionboundedbyasimpleclosedpolygonalcurveinZ2.AdominotilingofRcorrespondstoaperfectmatchingofG,thedualgraphofR:GhasavertexforeachlatticesquareinR,withtwoverticesadjacentifandonlyifthecorrespondinglatticesquaresshareanedge.Theorem1[Kasteleyn,1961]ThenumberofdominotilingsofRisp|detK|,whereKistheweightedadjacencymatrixofthegraphG,withhorizontaledgesweighted1andverticaledgesweightedi=√−1.∗LaboratoiredeMath´ematiques,UMR8628duCNRS,Bˆat425,Universit´eParis-Sud,91405Orsay,France.1Figure1:RandomtilingofasquareForexampleforthe2×3regioninFigure2,thematrixKisK=000i100001i100001ii100001i100001i000,whosedeterminanthasabsolutevalue9=32.236iii1115141Figure2:2×3rectangleanddualgraph.Proof:SincethegraphGisbipartite(onecancolorverticesblackandwhitesothatblackverticesareonlyadjacenttowhiteverticesandviceversa)KcanbewrittenK=0AAt0,2sowemustevaluatedetA=Xσ∈Snsgnσk1σ(1)...knσ(n)Eachterminthissumiszerounlessblackvertexσ(i)isadjacenttowhitevertexiforeachi.ThereforewehaveexactlyonetermforeachmatchingofG.Itsufficestoshowthattwononzerotermshavethesamesign.Supposewehavetwomatchings;drawthemoneontopoftheother.Theirsuperpositionisaunionof(doubled)edgesanddisjointcycles.Onecantransformthefirstmatchingintothesecondby“rotating”eachcycleinturn.Inparticularitsufficestoshowthatiftwomatchingsdifferonlyalongasinglecycle,thecorrespondingtermsinthedeterminanthavethesamesign.Thisissuppliedbythefollowinglemma,whichiseasilyprovedbyinduction.Lemma1LetC={v0,...,v2k−1,v2k=v0}beasimpleclosedcurveinZ2.Letm1betheproductoftheweightsonedgesv0v1,v2v3,...andm2theproductoftheweightsontheremainingedgesv1v2,...(recallthatverticaledgesareweightediandhorizontaledges1).Thenm1=(−1)n+k+1m2,wherenisthenumberofverticesstrictlyenclosedbycandkis1/2ofthelengthofc.2.2RectanglesSupposethegraphGisanmbynrectangle,withvertices{1,2,...,m}×{1,2,...,n}.Tocomputethedeterminantofitsadjacencymatrix,wecomputeitseigenvectorsandtheireigenvalues.Forj,k∈Zdefinef(x,y)=sinπjxm+1sinπkyn+1.ItiseasytocheckthatfisaneigenvectorofK,witheigenvalue2cosπjm+1+2icosπkn+1.Wedidn’tpullthisformulaoutofahat:sinceGisa“product”oftwolinegraphs,theeigenvectorsaretheproductoftheeigenvectorsofthelinegraphsindividually.Asj,kvaryoverintegersin[1,m]×[1,n],thefformanorthogonalbasisofeigenvectors.ThereforethedeterminantofKisdetK=mYj=1nYk=12cosπjm+1+2icosπkn+1.Evaluatingp|detK|form=n=8gives12988816tilingsofachessboard.Onemayshowthatform,nbothlargethenumberoftilingsisexp(Gmn/π+O(m+n)),whereG=1−132+152−172+...isCatalan’sconstant.32.3ToriItwillbeusefulshortlytocomputethenumberoftilingsforagraphonatorusaswell(e.g.arectanglewithitsoppositesidesidentified).Kasteleynshowedthatthiscouldbeaccom-plishedbyalinearcombinationoffourdeterminants.Inessencethesefourdeterminantscorrespondtothefourinequivalent“discretespinstructures”onthegraphGembeddedonthetorus.Ratherthangointodetails,wejustnotethattheaboveprooffailsonatorussincetwomatchingsmaydifferonaloopwhichgoesaroundthetorus(isnotnull-homologous).ThechangeinsigninthedeterminantfromonematchingtothenextisthenafunctionofthehomologyclassinH1(T,Z/2Z)oftheloop.Theresultisthat(form,nbotheven)thenumberoftilingsofanm×ntorusisZm,n=12(−P00+P01+P10+P11),wherePστ=Yzm=(−1)σYwn=(−1)τz+1z+iw+iw.NotethatactuallyP00=0inthiscase.Fordetailssee[8]or[4].Onecanshowthatlimm,n→∞1mnlogZm,n=Gπ.2.4InverseKasteleynmatrixWeareprimarilyinterestedintheuniformmeasureonperfectmatchingsofagraphG.AveryusefulconsequenceofKasteleyn’scountingtheoremisTheorem2([10])LetT={(w1,b1),...,(wk,bk)}beasubsetofdimers,(withthejthdimercoveringwhitevertexwjandblackvertexbj).TheprobabilitythatalldimersinTappearinauniformlychosenmatchingisPr(T)=|det(K−1(wi,bj))1≤i,j≤k|.TheadvantageofthisresultisthatthedeterminantforthejointprobabilityofkdimersisofsizekindependentlyofthesizeofthematrixK.Inparticulartocomputetheprobabilitythatasingleedgeappears,onejustneedsasingleelementofK−1.IfwecancomputeasymptoticsofK−1forlargerectangleswecanthenunderstandeasilythelimitingmeasuresontilingsoftheplane.We’lldothislater.Amoregeneralclassofmeasuresonperfectmatchingsusesgraphswithweightededges.Ifedgesarew