Perfect matchings for the three-term Gale-Robinson sequences

Perf e t m a things for the three-term Ga le -Robinson sequenes Mireille Bousquet-Mélou C NRS, LaBRI , Université Bordeaux 1 351 ours de la Lib ération ∗ James Propp University of Massahusetts Lowell MA 01854, USA 33405 Talene Cedex, Frane J a m e s P r o p p g m a i l . o m bousquetlabri.fr † Julian West Univers ity of Vitoria, PO Box 3060 Vitoria, BC V8W3R4, Canada juli a n j u l i a n w e st . a Submitted: Jun 17, 2009; Aepted: Sep 25, 2009; Published: Ot 5, 2009 M athematis Sub jet Classiation: 05A15, 05C70 In m emory of David Gale, 1921-2008 Abs trat In 1991, David Gale and Raphael Robinson, building on explorations arried out by M ihael Somos in the 1980s, intro dued a three-parameter family of ratio- nal reurrene relations , eah of whih (with suitable initial onditions) app eared to give rise to a s equene of integers, even though a priori the reurrene might pro due non- integral rational numb ers. Throughout the `90s, pro ofs of integrality we re known only for individual sp eial ases. In the early `00s, Sergey Fomin and A ndrei Z elevinsky proved G ale and Robinson`s integrality onjeture. They atu- ally proved muh more, and in partiular, that ertain bivariate rational funtions that generalize G ale- Robins on numb ers are atually p olynomials with integer o ef- ients . However, their pro of did not oer any enumerative interpretation of the Gale-Robinson numb ers/p olynomials. Here we provide suh an interpretation in the se tting of p erfet mathings of graphs, whih makes integrality/p olynomiality obvi- ous. Moreover, this interpretation implies that the o eients of the Gale-Robinson p olynomials are p os itive, as Fomin and Zelevinsky onjetured. ∗ JP was supp or ted by gr ants fr om the National Seurity Ageny and the National Siene Foundation. † JW was supp or ted by the National Sienes and Engineering Researh Counil of C anada. the electronic journal of combinatorics 16 (2009), #R125 1 1 Intro du tio n Lin e ar re urrenes a re ubiquito us in ombinatoris, as part of a broad general framework that is well- studied a nd well- understo o d; in partiular, many ombinatorially-dened se- q ue n e s an b e seen o n g enera l priniples to satisfy linear reurrenes (see [26℄), and onverse ly, when an integer sequene is known to satisfy a linear reurrene it is often p ossible to reverse- eng ineer a ombinatorial interpretation for the sequene (see [4℄ and re fere ne s therein f o r a g enera l disussion, and [3, Chapter 3℄ for sp ei examples). In ontrast, ratio na l reurrenes suh as s(n) = (s(n− 1)s(n−3)+s(n− 2)2)/s(n− 4), w hih we pref er to write in the fo rm s(n)s(n− 4) = s(n− 1)s(n−3)+s(n− 2)2, are e nountered f ar less of ten, and there is no simple general theory that desrib es the solu tion s to suh reurrenes o r relates those solutions to ombinatorial strutures. The p artiu lar ra tio na l reurrene rela tion given ab ove is the Somos-4 reurrene, and is part of a ge n eral f a mily o f reurrenes intro dued by Mihael Somos: s(n)s(n−k) = s(n−1)s(n−k+1)+s(n−2)s(n−k+2)++s(n−⌊k/2⌋)s(n−⌈k/2⌉). s(0) = s(1) = = s(k − 1) = 1 and denes subsequent terms using theIf on e p uts S omos- k reurrene, then o ne g ets a sequene of rational numb ers whih for the values k = 4,5,6,7 is a tua lly a sequene of integers. are entries A0 0 6 72 0 throug h A00 6 723 in [24℄.) (Sequenes Somos-4 through Somos-7 Although integer sequenes satisfying suh re urrenes have reeived a f air bit of attention in the past few years, until re- ently algebra rema ined one step a head of ombinatoris, and there was no enumerative inte rpretatio n o f these integ er sequenes. (For links related to Somos sequenes, see h tt p :/ / ja mespropp.org/somo s.ht ml .) In sp ire d by the wo rk of So mos, David Gale and Raphael R obinson [13, 12℄ onsidered se qu e ne s given by reurrenes of the form a(n)a(n− m) = a(n− i)a(n− j)+a(n −k)a(n −ℓ), a(0) = a(1) = = a(m−1) = 1 m = i+j = k+ℓ , where . We allw ith in itial o nditio ns 1 this the three-term Gale-Robi n son reur rene . The Somos-4 and Somos-5 reurrenes are the sp eia l a ses where (i,j,k,ℓ) (3,1,2,2) (4,1,3,2) and resp etively. Gale is equal to i,j,k,ℓ > 0 i + j = k + ℓ = m with , theand Rob in so n o nj etured tha t fo r all integers a(0),a(1),... determined by this reurrene has all its terms given by integers.se qu e ne A b ou t te n yea rs later, this wa s proved algebraially in an inuential pap er by Fomin and Zele v in sky [1 1 ℄. 1 a(n)a(n−m) = a(n−g)a(n−h)+a(n− G ale and Robins on als o ons ider ed r eurrenes of the form i)a(n − j) + a(n − k)a(n − ℓ) g,h,i,j,k,ℓ,m for s uitable values of , but suh four-term Gale-Robin son reurrenes will not b e our main oner n here. the electronic journal of combinatorics 16 (2009), #R125 2 1.1 Contents In th is pap er, we rst give a om binator ial pro of of the integrality of the three-term Gale -Robinso n sequenes. The integrality omes as a side-eet of pro duing a ombina- torial interpreta tion o f tho se sequenes. Sp eially, we onstrut a sequene of graphs P(n;i,j,k,ℓ) n > 0 n ( ) a nd prove in Theorem 9 that the th graph in the sequene has a(n) (p e rfet) ma thing s. Our g ra phs, whih we all pineones, generalize the well-known A zte d iamo nd g raphs, whih a re the mathings graphs for the Gale-R obinson sequene 1, 1, 2, 8, 6 4 , 1 0 24 , . . . i = j = k = ℓ = 1 . in whih A more generi example of a p ine on e is shown in Fig ure 1 . All pineones are subgraphs of the square grid. P(25;6,2,5,3) a(25) a(n) . Its mathing numb er isFigu re 1: The pineo ne is the, where (i,j,k,ℓ) = (6,2,5,3) . Gale -Robinso n sequene asso ia ted with We give two ways to onstrut pineones for the Gale-Robinson sequenes: a reursive P(n;i,j,k,ℓ) meth o d (see Fig ure 1 1 a nd the surrounding text) that onstruts the graph P(n′;i,j,k,ℓ) n′ < n in te rms of the sma ller gra phs , and a diret metho d (seewith P(n;i,j,k,ℓ) immediately.Formula (2) in Setio n 3 ) tha t a llows one to onstrut the graph a(n) T he heart o f o ur pro o f is the demonstration that if one denes as the numb er of P(n) ≡ P(n;i,j,k,ℓ) a(0),a(1),a(2),... p erfet mathing s o f satises the, the sequene Gale -Robinso n reurrene. This f a t, in ombination with a simple hek that a(0) = a(1) = = a(m − 1) = 1 , g ives an immediate indutive validation of our laim that P(n) a(n) n a(n) . , whih yields additionally the integrality ofp erfet ma thing s f o r all has Gen eral pineones a re dened in Setion 2, where we also explain how to ompute in du tive ly their ma thing numb er via Kuo`s ondensation lemma [17℄. In Setion 3, we d es rib e how to a sso ia te a sequene of pineones to a Gale-R obinson sequene, and obse rve th at f o r these pineo nes, the ondensation lemma sp eializes preisely to the Gale -Robinso n reurrene. Indeed, the reursive metho d of onstruting pineones, in omb in ation with Kuo `s ondensatio n lemma, gives ombinatorial meaning to the dierent te rms a(n )a(n ) of the Ga le- Robinson reurrene. p(n) ≡ p(n;w,z) In S e tio n 4 , we rene o ur arg ument to prove that the sequene d e n ed by p(n)p(n− m) = wp(n− i)p(n −j)+zp(n−k)p(n −ℓ), i+j = k+ℓ = m p(0) = p(1) = = p(m−1) = 1 a nd , is a sequene of p olynomialsw ith w z in with nonneg a tive integ er o eients. More preisely, we prove in Theorem 20an d that p(n;u2,v2) P(n;i,j,k,ℓ) by the numb er ofounts p erf et ma things of the pineone the electronic journal of combinatorics 16 (2009), #R125 3 u ) and the numb er of vertial edgess peial h orizo nta l edg es (the exp onent of the variable v p(n) (the ex p on ent o f the va ria ble is a p olynomial with o eients in). The fat that Z was p roved in [11℄, but no o mbinatorial explanation was given and the non-negativity of th e o eients wa s lef t o p en. 1.2 S trategy, and onne tio ns with pre vio us work For mu h o f the wo rk in this pap er, we share preedene with the students in the NS F-funded pro g ra m REACH (Researh E xp erienes in Algebrai Combinatoris at H arvard), led by James Pro pp, whose p ermanent arhive is on the web at h tt p :/ / ja mespropp.org/rea h/ . A pap er by one of these students, David Sp eyer [25℄, intro du ed a very exible f ra mewo rk (the rosses and wrenhes metho d) that, start- in g from a reurrene rela tio n o f a ertain typ e, onstruts a sequene of graphs whose mathin g numb ers sa tisf y the g iven reurrene. This framework inludes the three-term Gale -Robinso n reurrenes, a nd thus yields a ombinatorial pro of of the integrality of the asso iated sequenes. This extends to a pro of that the bivariate Gale-Robinson p olyno- ... - tailieumienphi.vn