Gale-Robinson sequenes
Mireille Bousquet-Mélou
CNRS, LaBRI,Université Bordeaux1
351ours dela Libération
33405 Talene Cedex,Frane
bousquetlabri.fr
James Propp
∗
Universityof MassahusettsLowell
MA01854, USA
JamesProppgmail.om
Julian West
†
UniversityofVitoria, POBox3060
Vitoria,BCV8W3R4, Canada
julianjulianwest.a
Submitted: Jun 17,2009;Aepted: Sep 25,2009; Published: Ot 5,2009
Mathematis SubjetClassiation: 05A15, 05C70
In memoryof David Gale, 1921-2008
Abstrat
In 1991, David Gale and Raphael Robinson, building on explorations arried
out by Mihael Somos in the 1980s, introdued a three-parameter family of ratio-
nal reurrene relations, eah of whih (with suitable initial onditions) appeared
to give rise to a sequene of integers, even though a priori the reurrene might
produe non-integral rational numbers. Throughout the '90s, proofs of integrality
were known only for individual speial ases. In the early '00s, Sergey Fomin and
Andrei Zelevinsky proved Gale and Robinson's integrality onjeture. They atu-
ally proved muh more, and in partiular, that ertainbivariate rational funtions
that generalize Gale-Robinson numbers areatually polynomials with integer oef-
ients. However, their proof did not oer any enumerative interpretation of the
Gale-Robinsonnumbers/polynomials. Hereweprovidesuhaninterpretationinthe
settingof perfet mathings ofgraphs, whih makesintegrality/polynomialityobvi-
ous. Moreover,this interpretationimpliesthattheoeientsoftheGale-Robinson
polynomials arepositive,asFomin and Zelevinskyonjetured.
∗
JPwassupportedbygrantsfromtheNationalSeurityAgenyandtheNationalSieneFoundation.
†
JWwas supportedbytheNationalSienesand EngineeringResearhCounilofCanada.
Linear reurrenes are ubiquitousinombinatoris,as partof abroad generalframework
that is well-studied and well-understood; in partiular,many ombinatorially-dened se-
quenes an be seen on general priniples to satisfy linear reurrenes (see [26℄), and
onversely, when an integer sequene is known to satisfy a linear reurrene it is often
possible to reverse-engineer a ombinatorialinterpretation for the sequene (see [4℄ and
referenes therein for a general disussion, and [3, Chapter 3℄ for spei examples). In
ontrast, rationalreurrenes suhas
s(n) = (s(n − 1)s(n − 3) + s(n − 2) 2 )/s(n − 4),
whihwe prefer to write inthe form
s(n)s(n − 4) = s(n − 1)s(n − 3) + s(n − 2) 2 ,
are enountered far less often, and there is no simple general theory that desribes the
solutions to suh reurrenes or relates those solutions to ombinatorial strutures. The
partiular rationalreurrene relationgiven aboveis the Somos-4reurrene, and ispart
of a generalfamily of reurrenes introduedby 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⌉).
If one puts
s(0) = s(1) = · · · = s(k − 1) = 1
and denes subsequent terms using theSomos-
k
reurrene, then one gets a sequene of rational numbers whih for the valuesk = 4, 5, 6, 7
is atually a sequene of integers. (Sequenes Somos-4 through Somos-7are entries A006720 through A006723 in [24℄.) Although integer sequenes satisfying
suh reurrenes have reeived a fair bit of attention in the past few years, until re-
ently algebra remained one step ahead of ombinatoris, and there wasno enumerative
interpretation of these integer sequenes. (For links related to Somos sequenes, see
http://jamespropp.org/somo s.ht ml.)
Inspired by the workof Somos,DavidGale and RaphaelRobinson[13,12℄ onsidered
sequenes given by reurrenes of the form
a(n)a(n − m) = a(n − i)a(n − j) + a(n − k)a(n − ℓ),
withinitialonditions
a(0) = a(1) = · · · = a(m − 1) = 1
,wherem = i+ j = k +ℓ
. Weallthis the three-term Gale-Robinson reurrene 1
. The Somos-4 and Somos-5 reurrenes
arethespeialaseswhere
(i, j, k, ℓ)
isequalto(3, 1, 2, 2)
and(4, 1, 3, 2)
respetively. Gale and Robinson onjetured that for all integersi, j, k, ℓ > 0
withi + j = k + ℓ = m
, thesequene
a(0), a(1), . . .
determined by this reurrene has all itsterms given by integers.About ten years later,this wasproved algebraiallyinaninuentialpaperby Fominand
Zelevinsky [11℄.
1
GaleandRobinsonalsoonsideredreurrenesoftheform
a(n)a(n − m) = a(n − g)a(n − h) + a(n −
i)a(n − j) + a(n − k)a(n − ℓ)
for suitable values ofg, h, i, j, k, ℓ, m
, but suh four-term Gale-Robinson reurreneswillnotbeourmain onernhere.In this paper, we rst give a ombinatorial proof of the integrality of the three-term
Gale-Robinsonsequenes. The integrality omes asa side-eetof produinga ombina-
torial interpretation of those sequenes. Speially, we onstrut a sequene of graphs
P (n; i, j, k, ℓ)
(n > 0
) and prove in Theorem 9 that then
th graph in the sequene hasa(n)
(perfet)mathings. Ourgraphs,whihweallpineones,generalize thewell-knownAzte diamondgraphs, whih are the mathings graphs for the Gale-Robinsonsequene
1, 1, 2, 8, 64, 1024, ... in whih
i = j = k = ℓ = 1
. A more generi example of apineone is shown in Figure1. All pineones are subgraphs of the square grid.
Figure 1: The pineone
P (25; 6, 2, 5, 3)
. Its mathing numberisa(25)
, wherea(n)
is theGale-Robinsonsequene assoiated with
(i, j, k, ℓ) = (6, 2, 5, 3)
.WegivetwowaystoonstrutpineonesfortheGale-Robinsonsequenes: areursive
method (seeFigure11and the surroundingtext) that onstrutsthe graph
P (n; i, j, k, ℓ)
in terms of the smaller graphs
P (n ′ ; i, j, k, ℓ)
withn ′ < n
, and a diret method (seeFormula(2)inSetion3)thatallowsonetoonstrutthegraph
P (n; i, j, k, ℓ)
immediately. The heart of our proof is the demonstration that if one denesa(n)
as the number ofperfet mathings of
P (n) ≡ P (n; i, j, k, ℓ)
, the sequenea(0), a(1), a(2), ...
satises theGale-Robinson reurrene. This fat, in ombination with a simple hek that
a(0) = a(1) = · · · = a(m − 1) = 1
, gives an immediate indutive validation of our laim thatP (n)
hasa(n)
perfetmathingsforalln
,whihyieldsadditionallytheintegralityofa(n)
.General pineones are dened in Setion 2, where we also explain how to ompute
indutively their mathing number via Kuo's ondensation lemma [17℄. In Setion 3,
we desribe how to assoiate a sequene of pineones to a Gale-Robinson sequene, and
observe that for these pineones, the ondensation lemma speializes preisely to the
Gale-Robinson reurrene. Indeed, the reursive method of onstruting pineones, in
ombinationwithKuo'sondensationlemma,givesombinatorialmeaningtothedierent
terms
a(n 1 )a(n 2 )
of the Gale-Robinsonreurrene.In Setion 4, we rene our argument to prove that the sequene
p(n) ≡ p(n; w, z)
dened by
p(n)p(n − m) = w p(n − i)p(n − j) + z p(n − k)p(n − ℓ),
with
i + j = k + ℓ = m
andp(0) = p(1) = · · · = p(m − 1) = 1
,isasequene ofpolynomials inw
andz
withnonnegative integeroeients. More preisely, weprove inTheorem 20 thatp(n; u 2 , v 2 )
ountsperfet mathings ofthe pineoneP (n; i, j, k, ℓ)
by the numberofspeial horizontaledges(theexponentof the variable
u
)and the numberofvertialedges(the exponent of the variable
v
). The fat thatp(n)
is a polynomial with oeients inZ
wasproved in[11℄, but noombinatorialexplanation wasgiven and the non-negativity of the oeients was left open.1.2 Strategy, and onnetions with previous work
For muh of the work in this paper, we share preedene with the students in
the NSF-funded program REACH (Researh Experienes in Algebrai Combinatoris
at Harvard), led by James Propp, whose permanent arhive is on the web at
http://jamespropp.org/rea h/. A paper by one of these students, David Speyer [25℄,
introdued a very exible framework (the rosses and wrenhes method) that, start-
ing from a reurrene relation of a ertain type, onstruts a sequene of graphs whose
mathing numbers satisfy the given reurrene. This framework inludes the three-term
Gale-Robinsonreurrenes, and thusyieldsaombinatorialproof ofthe integrality ofthe
assoiated sequenes. This extends to a proof that the bivariate Gale-Robinson polyno-
mials mentioned above are indeed polynomials, and have non-negative oeients. One
dierenewithourpaperisthatSpeyer'sgraphsareonlydesribed expliitlyforSomos-4
and Somos-5 sequenes, whereas our onstrution is expliit for any Gale-Robinson se-
quene. Moreover, the desription of our graphs as subgraphs of the square grid looks
moreregular,and may beuseful tostudy limitshapesofrandomperfetmathings. Fig-
ure 19 shows two random perfet mathings assoiated with the Somos-4 sequene (or,
rather, the equivalentdomino tilings).
LetusmentionthatshortlyafterSpeyerdidhisworkonperfet mathings,he andhis
fellow REACH-partiipant Gabriel Carroll did for four-term Gale-Robinson reurrenes
what Speyer had done for three-term Gale-Robinson reurrenes, by introduing new
objets alled groves to take the plae of perfet mathings [6℄. Carroll and Speyer's
work gives, as two speial ases, ombinatorial proofs of the integrality of Somos-6 and
Somos-7.
ThestrategiesthatledtoSpeyer'sartile[25℄andtothepresentartilearenotentirely
independent; eah made use of Propp's prior onstrution of a suitable perturbed Gale-
Robinson reurrene, whih we explain next. The explanation will mostly be of interest
toresearhers seeking toapply similar tehniques to otherproblems; others may want to
skip the rest of the introdution.
Suppose we perturb a three-term Gale-Robinson reurrene by replaing the singly-
indexedGale-Robinsonnumber
a(n)
byatriply-indexed quantityA(n, p, q)
satisfyingtheperturbed reurrene
A(n, p, q)A(n−m, p, q) = A(n−i, p−1, q)A(n−j, p+1, q)+A(n−k, p, q+1)A(n−ℓ, p, q−1).
(This hoie of perturbation is not as speial as it looks: all that matters is that the
pairs
(−1, 0), (1, 0), (0, 1), (0, −1)
that desribe the perturbations of the seondand third oordinates inthe fourindex-triples onthe right-handside, viewed aspointsintheplane,symmetri parallelogramis tantamount to asimple re-indexing of the reurrene.) Ifwe
take as our initial onditions
A(n, p, q) = x n,p,q for all n
between 0 and m − 1
and p, q
arbitrary, with (formal) indeterminates
x n,p,q, then eah A(n, p, q)
with n > m
an be
expressed as a rational funtion of these indeterminates. It should be emphasized here
thatforall
n, p, q, r, s
,therationalfuntionsA(n, p, q)
andA(n, r, s)
arethesamefuntionup to re-indexing of the indeterminates.
Propponjeturedthateah
A(n, p, q)
isaLaurentpolynomialinsome nitesubsetofthe(innitelymany)indeterminates
x n,r,s,withintegeroeients;thatis,eahA(n, p, q)
is an element of
Z [x ± n,r,s 1 ]
. This was subsequently proved by Fomin and Zelevinsky [11℄.Note that if one sets all the indeterminates
x n,r,s equal to 1, the Laurent polynomials
A(n, p, q)
speialize to the Gale-Robinson numbersa(n)
. Propp onjetured that eahoeientineahsuhLaurentpolynomialispositive(afatthatisnot proved byFomin
and Zelevinsky's method)and furthermore is equal to
1
.Proppknewthatinthease
i = j = k = ℓ = 1
,the LaurentpolynomialsA(n, p, q)
anbeinterpretedasmultivariatemathingpolynomialsofsuitablegraphs,namely,theAzte
diamond graphs. (See Subsetion 2.1 for a denition of mathing polynomials.) Indeed,
David Robbins had studied the three-parameter perturbed reurrene in this ase, on
aount of its relationto the study of determinants, and had shown (with Rumsey) [22℄
that the assoiated rational funtions are Laurent polynomials. (For more bakground
on this onnetion with determinants, see [5℄.) The work by Elkies, Kuperberg, Larsen,
and Propp [10℄ had shown that the monomialsin these Laurent polynomials orrespond
to perfet mathings of Azte diamond graphs. So it was natural to hope that this
orrespondene ouldbeextended tothe Gale-Robinson family of reurrenes.
It should be aknowledged here that the idea behind the spei triply-indexed per-
turbation
A(n, p, q)
of the Gale-Robinsonsequene that proved so fruitful ame from an artile of Zabrodin [28℄ that was brought to Propp's attention by Rik Kenyon. Thisartileled Propp tothink that the reurrenestudied by Robbinsshouldbeonsidered a
speial ase of the disrete bilinearHirota equation,orotahedronequation,and that
other reurrenes suh as the Gale-Robinsonreurrene shouldlikewise be onsidered in
the ontext of the otahedron equation.
What the REACHstudents wereable todo, afterdiligentexaminationof theLaurent
polynomials
A(n, p, q)
,is viewthose Laurent polynomialsas multivariatemathingpoly- nomials of suitable graphs. Bousquet-Mélou and West, independently, did the same forsmall values of
n
, untilthey were able to extrapolate these examplesto the generi form of the graphs, whih beame the pineones of this paper.There is a general strategy here for reverse-engineering ombinatorial interpretations
of algebraially-dened sequenes of numbers: add suiently many extra variables so
that the numbers beome Laurent polynomials in whih every oeient equals 1. For
anotherappliationofthisreverse-engineeringmethod(intheontextofMarkonumbers
and frieze patterns), see [18℄.
In this setion we dene a family of subgraphs of the square lattie, whih we all
pineones. Then we prove that the number of perfet mathings of a pineone an be
omputed indutively in terms of the number of perfet mathings of ve of its sub-
pineones.
2.1 Preliminaries
To begin with, let us reall some terminology about graphs. A (simple) graph
G
is anorderedpair
(V, E )
whereV
isanitesetofverties,andE
,thesetofedges,isaolletionof2-elementsubsetsof
V
. Thedegreeofavertexv
isthenumberofedgesinE
ontainingv
. AsubgraphofG
isagraphH = (V ′ , E ′ )
suhthatV ′ ⊂ V
andE ′ ⊂ E
. If,inaddition,V ′ = V
, we say thatH
is a spanning subgraph ofG
. The intersetion of two graphsG = (V, E)
andH = (V ′ , E ′ )
is the graphG ∩ H = (V ∩ V ′ , E ∩ E ′ )
, and the union ofthe two graphsisthe graph
G ∪ H = (V ∪ V ′ , E ∪ E ′ )
. Given twographsG = (V, E)
andH = (V ′ , E ′ )
, we denotebyG \ H
the subgraph(V ′′ , E ′′ )
, whereV ′′ = V \ V ′ and E ′′ is
the set of edges of
E \ E ′ havingboth endpoints inV ′′.
A perfet mathing of agraph
G = (V, E)
is a subsetE ′ of E
suh that every vertex
of
V
belongs to exatly one edge ofE ′. We willsometimes omit the word perfet and
refertoperfet mathings assimplymathings. The mathingnumber of
G
,denoted bym(G)
, is the number of perfet mathings ofG
. More generally, we shall often onsiderthe set
E
of edges as a set of ommuting indeterminates, and assoiate with a (perfet) mathingE ′ the produt of the edges it ontains. The mathing polynomial of G
is thus
dened to be
M (G) := X
E ′
Y
e ∈ E ′
e,
where the sum runs overall perfet mathings
E ′ of G
. If wereplae every e
that ours
inthissum-of-produtsbyanon-negativeinteger
n e,thenthis expressionbeomesanon-
negative integer, namely, the number of perfet mathings of the multigraph in whih
there are
n e edges joining the verties x
and y
for all e = {x, y}
in E
(and no edges
joining
x
andy
if{x, y}
isnot inE
). In partiular, if eahn e is set equal to0or 1,then
the mathingpolynomial beomesthe numberof perfet mathingsof the subgraph of
G
onsisting of preisely those edges
e
for whihn e = 1
.2.2 Azte diamonds graphs
The pineones onsidered in this paper are ertain subgraphs of the square lattie. The
mostregularofthemare the(Azte) diamondgraphs,whihare thedualsof theso-alled
Azte diamonds, whih were rst studied in detail in [10℄. A diamond graph of width
2k − 1
is obtained by taking onseutive rows of squares, of length1, 3, . . . , 2k − 3, 2k − 1, 2k −3, . . . , 3, 1
andstakingthemfromtoptobottom,withthemiddlesquaresinalltherows lining up vertially, asillustrated by Figure 2. Let
A
be a diamondgraph of width9
e
s n
w
Figure 2: An Azte diamondgraph of width
9
,and one of itsperfet mathings.2k − 1
. LetA N bethe diamondgraphof width 2k − 3
obtained by deletingthe leftmost
and rightmost squares of
A
as well as the two lowest squares of eah of the remaining2k − 3
olumns ofA
. We allA N the North sub-diamond of A
. Dene similarly the
South, West and East sub-diamonds of
A
, denoted byA S , A W and A E. Finally, let A C
A C
be the entral sub-diamond of
A
of width2k − 5
(Figure 3). The following result is areformulationof Kuo's ondensationtheorem for Azte diamondgraphs [17℄.
Theorem 1 (Condensation for diamonds graphs) The mathing polynomial of a
diamond graph
A
is related to the mathing polynomials of its sub-diamondsbyM(A)M (A C ) = nsM (A W )M (A E ) + ewM (A N )M (A S ),
where
n, s, w,
ande
denote respetively thetop (resp. bottom, westmost,eastmost)edge ofA
(see Figure 2).In partiular, if
a(n)
(withn > 2
) denotes the mathing number of a diamond graph ofwidth
2n − 3
,thena(n)a(n − 2) = 2a(n − 1) 2
for all
n > 2
, provided we adopt the initialonditionsa(0) = a(1) = 1
. This shows thata(n)
is the three-term Gale-Robinson sequene assoiated withi = j = k = ℓ = 1
, andimplies
a(n) = 2( n 2 )
.
The ondensation theorem we shall prove for pineones appears as a generalization
of the ondensation theorem for diamond graphs. But it an atually also be seen as a
speialization of it,and this is the point of viewwe adopt in this paper. The key idea is
toforbid ertainedges in the mathings.
Corollary 2 Let
A
beadiamondgraph,andletG
beaspanningsubgraphofA
,ontainingthe edges
n, s, w
ande
. LetG N = G ∩ A N, and dene G S , G W , G E and G C similarly.
G C similarly.
Then
M (G)M(G C ) = nsM(G W )M (G E ) + ewM (G N )M (G S ).
A E
A W A C
A N
A S
Figure3: The ve sub-diamondsof a diamondgraph of width
9
.Proof. Sine
G
is a spanning subgraph ofA
, every perfet mathing ofG
is a perfetmathing of
A
. Hene the mathing polynomialM (G)
is simply obtained by settinga = 0
inM (A)
, for every edgea
that belongs toA
but not toG
. The same propertyrelates
M (G N )
andM (A N )
, and so on. Consequently, Corollary 2 issimplyobtained by settinga = 0
in Theorem 1,for every edgea
that belongstoA
but not toG
.2.3 Pineones: denitions
A standard pineone of width
2k − 1
is a subgraphP = (V, E)
of the square lattiesatisfyingthe three following onditions,illustrated by Figure4.
a
:1.
Thehorizontaledges formi + j + 1
segmentsof oddlength, startingfromthepoints(0, 1), (1, 2) . . . , (i − 1, i)
and(0, 0), (1, −1), . . . , (j, −j)
,forsomei > 1
,j > 0
. More-over, if
L m denotes the length of the segment lyingat ordinatem
, then
L − j < · · · < L − 1 < L 0 = 2k − 1 = L 1 > L 2 > · · · > L i .
2.
The set of vertiesV
is the set of verties of the square lattiethat are inident tothe above horizontaledges.
3.
Lete = {(a, b), (a, b + 1)}
beavertialedgeofthesquare lattiejoiningtwovertiesof
V
. Ifa + b
is even, thene
belongs tothe set ofedgesE
, and we say thate
is aneven edgeof
P
. Otherwise,e
may belong toE
,or not (Figure4.a
), and we alle
a(present orabsent) odd edge.
The leftmostverties ofa standard pineone are always
(0, 0)
and(0, 1)
. However, some-times it isonvenient to onsider graphsobtained by shifting suh a graph toa dierent
loationinthe two-dimensionallattie. Wewillallsuhagraphatransplantedpineone.
In a transplanted pineone, the leftmost verties are
(a, b)
and(a, b + 1)
, wherea + b
iseven. In some ases, where the distintion between standard and transplanted pineones
is not relevant or where we think the ontext makes it lear whih sort of pineone we
intend, we omit the modier and simplyuse the word pineone.
b. c.
a.
(0, 0)
Figure4: Somepineones of width
15
.a
. The dashededges may belong tothe graph, ornot.
b
. A pineone.c
. A losed pineone.Figures4.
b
and 4.c
show twospei ways tomakethe hoiesindiated inFigure4.a
and obtain apineone of width 15. The pineone of Figure 4.
c
is losed,meaning that itontains no vertex of degree
1
. (Suh a vertex an only our at the right border of thepineone, and ours if the rightmost vertex of some horizontalsegment does not belong
to a vertial edge, as shown in Figure 4.
b
.) An Azte diamond graph is an example ofa losed pineone. Let us olor the ells of the square lattie alternatingly in blak and
white in suh a way that the ell ontaining the verties
(0, 0)
and(1, 1)
is blak. Thefaesofthe pineoneare theniteonneted omponentsoftheomplementofthegraph
in
R 2. The faes of a pineone P
are of three types: blak squares, white squares, and
horizontalretanglesonsistingof ablakelltotheleftandawhiteelltotheright. We
insist onthe distintion between aell (ofthe underlyingsquare lattie)and asquare (a
fae of
P
that has 4 edges). For instane, the longest row of a pineone of width2k − 1
ontainsexatly
2k − 1
ells, butmayontainnosquareatall. Denotingbyℓ
(resp.r
)theleftmost (resp. rightmost) ell of the longest row of
P
, we say thatP
is rooted on(ℓ, r)
.(If
P
is standard, thenℓ
is the ell with(0, 0)
as its lower-left orner.) We refer to thelongest row of a pineone as row
0
. The row above it (resp. below) is row1
(resp.−1
),and so on.
It is easy tosee that a pineone
P
is losed if and onlyif the rightmost nite fae ofeahrowisablak square. In thisase,the rightmostblaksquareineahrowisalsothe
rightmost ell of the row. If moreover
P
is standard, it is ompletelydetermined by theposition of itsblak squares. Equivalently,it isompletely determinedby the positionof
itsodd vertial edges. Conversely, onsider any nite set
S
of blaksquares whoselower-left verties lie in the 90 degree wedge bounded by the rays
y = x > 0
and−y = x > 0
.Assume that
S
is monotone, in the following sense: the rows that ontain at least onesquareof
S
areonseutive(sayfromrow−j
torowi
, whererowm
referstoellsloatedbetween ordinates
m
andm + 1
)andform > 0
(resp.m < 0
),the rightmostblaksquareinrow
m
ourstothe leftoftherightmostblaksquare inrowm − 1
(resp.m + 1
). Thenis a(unique) losed standard pineone whose set of blak squares is
S
.We shall often onsider the empty graph as a partiular losed pineone (assoiated
with the empty set of blak squares). The empty graph has one perfet mathing, of
weight 1.
2.4 The ore of a pineone
When a pineone
P
is not losed, some of the edges ofP
annot belong to any perfetmathingof
P
. Speially,ifv
isavertex ofdegree1 inP
,theninany perfet mathingof
P
,v
must be mathed with the vertex to its left (all itu
), so thatu
annot bemathed with any of its other neighbors. Indeed, there an be a hain reation whereby
a fored edge, in ausing other edges to be forbidden, leads to new verties of degree 1,
ontinuingthe proessofforing andforbiddingotheredges. Anexampleof thisisshown
inFigure5. Thelefthalfofthe pitureshows anon-losedpineone
P
,andthe righthalfof thepitureshows a losedsub-pineone
P ¯
ofP
alongwith aset of isolatededges. Thereader an hek (starting from the rightmost frontier of
P
and working systematially leftward) that eah of the isolated edges is a fored edge (that is, it must be ontainedin every perfet mathing of
P
), so that a perfet mathing ofP
is nothing other thana perfet mathing of
P ¯
together with the set of isolated edges shown at right. In thissubsetion, we will give a systemati way of reduing a pineone
P
to a smaller losedpineone by pruning away some fored and forbidden edges.
Figure5: From apineone
P
to itsoreP ¯
.It an easilybe heked that the union or intersetion of two standard pineones is a
standard pineone, and that the union or intersetion of two losed standard pineones
is a losed standard pineone. It follows that, if
P
is a standard pineone, there exists alargest losed standard sub-pineone of
P
, namely, the union of all the losed standardsub-pineones of
P
. Weallthisthe ore ofP
anddenoteitbyP ¯
. (IfP
isnotastandardpineone but a transplanted pineone rooted at the ell with lower-left orner
(a, b)
, wedene
P 0 asthe standard pineone obtained by translating P
by (−a, −b)
, and we dene
the ore of
P
asthe ore ofP 0 translated by (a, b)
. However, for the rest of this setion
we willrestrit attention to standard pineones.)
Here is an alternative (more onstrutive and less abstrat) approah todening the
ore. Let
P
be a standard pineone. Letb 0 be the rightmost blak square in row 0 of
P
, letb 1 be the rightmost blak square in row 1 of P
that lies stritly to the left of b 0,
let
b 2 be the rightmost blak square in row 2 of P
that lies stritly tothe left of b 1, and
so on(proeedingupwards); likewise, let
b − 1 be the rightmost blak square in row −1
of
P
that liesstritly to the leftof b 0, and so on(proeeding downwards). If atsome point
there is no blak square that satises the requirement, we leave b m undened. Consider
b m undened. Consider
all the faes of
P
that lie in the same row as,and lieweakly tothe left of, one of one ofthe
b k's. Thisset offaesgivesalosedpineone P ˜
. Atthe sametime,itislearthatany
losedsub-pineone
Q
ofP
must beasub-pineone ofP ˜
. For,the rightmostblaksquarein row 0 of
Q
an be no farther to the right thanb 0, whih implies that the rightmost
blak square in row 1 of
Q
an be no farther to the right thanb 1, et.; and likewise for
the bottom half of
Q
. Hene the sub-pineoneP ˜
we haveonstruted is none otherthanthe ore of
P
as dened above.If
P
is losed, thenP ¯ = P
. Note that a losed pineone always admits two partiu-larlysimple perfet mathings: one onsisting entirelyof horizontaledges, and the other
onsisting of the leftmostand rightmost vertial edgesin eah row(and noother vertial
edges) along with some horizontal edges (Figure6). In partiular, the rightmost vertial
edges of a losedpineone are never fored nor forbidden.
Figure 6: Two partiularlysimple mathingsof a losed pineone.
Let
P
be a pineone with oreP ¯
. There is a unique perfet mathing ofP \ P ¯
onsisting exlusively of horizontal edges (see Figure 5); let
H
be the edge set of thisperfet mathing. Every perfet mathing of
P ¯
an be extended to a perfet mathingof
P
by adjoining the edges inH
, som(P ) > m( ¯ P )
. We now show that every perfetmathing of
P
is obtained froma perfet mathing ofP ¯
inthis way.Proposition 3 Let
P
be a pineone with oreP ¯
. Thenm( ¯ P ) = m(P )
.Proof. Wewillprovethis laim by usinga proedure that redues asub-pineone
Q
ofP
toasmallersub-pineone with thesamemathingnumber. Let
Q
beasub-pineoneofP
whoseore oinides with
P ¯
. IfQ
isnot losed,then theremust beatleast onevertex ofdegree1alongtherightboundaryof
Q
. Letv = (a, b)
beoneofthetherightmostvertiesof degree
1
inQ
. Thenv
isthe rightmost vertex inone of the rows ofQ
. Assume for themoment that
v
lies stritly above the longestrowofQ
(that is,b > 1
). See the top partof Figure7 for anillustration of the following argument. Let
u
be the vertex to the leftof
v
. Then the edge joiningu
andv
is fored to belong to every perfet mathing ofQ
,while every other edge ontaining
u
is forbiddenfrom belongingto any perfet mathingof
Q
. Hene thegraphQ ′ obtained fromQ
bydeletingu
, v
,and every edgeinidentwith
u
or v
has the same mathing number as Q
. Furthermore, Q ′ is a pineone, unless the
vertex
v 1 = (a − 1, b + 1)
belongs toQ
. In this ase,v 1 has degree 1 in Q ′. Let i
be the
i
be thelargest integer suh that
v j = (a − j, b + j)
belongs toQ
for all0 6 j 6 i
. Applying thedeletion proedure to the verties
v = v 0 , v 1 , . . . , v i (in this order) yields a pineone Q ∗.
Assume now that
b = 1
. Applying the deletion proedure to all the verties ofQ
of theform
(a − j, 1 + j)
or(a − j, −j )
yields again a pineoneQ ∗ (see Figure 7, bottom). By
symmetry,wehave overed allpossible values of
b
.v v 2
v 1
v
v 2
v 1
v
v Q
Q
Q ∗
Q ∗
Figure7: Some sequenes of edge-deletions startingand ending with apineone.
Observethat
m(Q) = m(Q ∗ )
. Additionally,weanhekthattheoreofQ ∗ isP ¯
. The
onlythingwemightworryabout isthatinpassingfrom
Q
toQ ∗,weremoved someedges
that belong to
P ¯
. The examination of Figure5 shows that we would have, inpartiular, removed the rightmost vertial edge is some row ofP ¯
. However, this annot happen,beause the removed edges were all fored or forbidden, whereas the rightmost edges of
P ¯
are neitherfored nor forbidden(Figure6).To prove that
m( ¯ P ) = m(P )
,takeQ = P
and use the preedingoperationrepeatedlytoonstrut suessively smallergraphs
Q ∗, Q ∗∗, ...suhthat m(P ) = m(Q) = m(Q ∗ ) = m(Q ∗∗ ) = · · ·
and P ¯ = ¯ Q = Q ∗ = Q ∗∗ = · · ·
. Eventually we arrive at a losed sub-
m(P ) = m(Q) = m(Q ∗ ) = m(Q ∗∗ ) = · · ·
andP ¯ = ¯ Q = Q ∗ = Q ∗∗ = · · ·
. Eventually we arrive at a losed sub-pineone of
P
whose ore isP ¯
; that is, we arrive atP ¯
itself. And sine eah step of ouronstrution preserves
m(Q)
,weonlude thatm( ¯ P ) = m(P )
,as laimed.Let
P
be a losed pineone, with longest row onsisting of2n + 1
squares. LetA
be thesmallestdiamondgraphontaining
P
(thelongestrowofA
ontains exatly2n + 1
ells).Let
G
denote the spanning subgraph ofA
whose edge-set onsists of all edges ofP
, allhorizontal edges of
A
, and all even vertial edges ofA
(Figure 8). Observe thatG
is apineone. Moreover, amongthe spanning subgraphs of
A
that are pineones and ontainP
,G
has stritly fewer edges than the others. Sine no odd vertial edge is added,P
isatually the ore of the pineone
G
.P G
Figure8: Completingapineone
P
intoaspanning pineoneof anAztediamondgraph.Let usnow use the notationof Corollary 2. That is,
G N = G ∩ A N,and soon. Then
G N , G S , G W , G E andG C are (standardortransplanted)pineones. LetP N,P S,P W,P E
P N,P S,P W,P E
P W,P E
and
P C denote theirrespetiveores. (These are nottobeonfusedwith P N,et., whih
are theintersetionsof
P
withA N,et.) WewilloftenallP N,P S,P W, P E and P C the
P S,P W, P E and P C the
P E and P C the
ve sub-pineones of
P
, even though, stritly speaking,P
admits other sub-pineones.An example is given in Figure9. Let
ℓ 0 (resp. r 0) be the leftmost (resp. rightmost) ell
of the longest row
R 0 of P
. Similarly,let r 1 (resp. r − 1) denote the rightmost ellof the
r − 1) denote the rightmost ellof the
row just above (resp. below)
R 0. Observe that the ells r 0 , r 1 and r − 1 orrespond to
r − 1 orrespond to
blak squares of
P
. Finally, letℓ ′ 0 be the blak ell of R 0 following ℓ 0, and let r 0 ′ the
ℓ 0, and let r 0 ′ the
blak square of
R 0 preeding r 0 (if it exists). In light of the basi properties of the ore
(both theabstrat denition andthe algorithmionstrution), wean givethe following
alternative desription of the ve sub-pineones of
P
.Proposition 4 Let
P
be a losed pineone. With the above notation,P N (resp. P S) is
the largest losed sub-pineone of
P
whoserightmost ell isr 1 (resp.r − 1). Similarly, P W
P W
(resp.
P E) is the largest losed sub-pineone whose rightmost (resp. leftmost) ell is r 0 ′
(resp.
ℓ ′ 0). Finally, P C is the largest losed sub-pineone rooted on (ℓ ′ 0 , r 0 ′ )
.
(ℓ ′ 0 , r 0 ′ )
.This propositionimplies that apineone
P
that isneither empty, nor redued to ablaksquare an be reonstruted from its four main sub-pineones
P N, P S, P E and P W.
P E and P W.
Indeed, thepart of
P
loatedstritlyabove itslongestrowoinides with the top partofP C P N
P E P W
P S
r − 1
ℓ 0
r 1
r 0 r ′ 0
ℓ ′ 0
Figure 9: The ve sub-pineones of apineone
P
.P N. More preisely, row r
of P
, with r > 0
oinides with row r − 1
of P N. Similarly,
for
r < 0
, rowr
ofP
oinides with rowr + 1
ofP S. It thus remains to determine the
longest row of
P
. This row is obtained by adding a2
-by-1
retangle2 to the left of thelongest rowof
P E,and thensuperimposing the longest rowof P W.
LetusnowapplyCorollary2tothegraph
G
obtainedbyompletingP
intoaspanningpineone of
A
(Figure8). ByProposition3, sineP
isthe ore ofG
,m(G) = m(P )
,andsimilar identities relate the mathing numbers of
G N and P N, et.
Theorem 5 (Condensation for losed pineones) Themathingnumber of a losed
pineone
P
is related to the mathing number of its losed sub-pineones bym(P )m(P C ) = m(P W )m(P E ) + m(P N )m(P S ).
Wewill state in Setion4 a more general ondensationresult dealing with the mathing
polynomial, ratherthan the mathings number, of losed pineones (Theorem 13).
3 Pineones for the Gale-Robinson sequenes
The pineones introduedin the previous setiongeneralize Azte diamondgraphs. The
numberof perfet mathings ofthe diamondgraphofwidth
2n − 3
isthen
thterminthe2
Thisretangleisatuallyonlyusefulif
P W
isemptyorreduedtoasingleblaksquare.a(n)a(n − 2) = a(n − 1)a(n − 1) + a(n − 1)a(n − 1),
with initial onditions
a(0) = a(1) = 1
. More generally, the three-term Gale-Robinson sequenes are governed by reurrenes of the forma(n)a(n − m) = a(n − i)a(n − j) + a(n − k)a(n − ℓ),
(1)with initial onditions
a(n) = 1
forn = 0, 1, . . . , m − 1
. Here,i, j, k
andℓ
are positiveintegers suhthat
i + j = k + ℓ = m
, and weadopt the following(important)onventionj = min{i, j, k, ℓ}.
Ourpurposeinthissetionistoonstrutasequeneof(losed)pineones
(P (n)) n> 0 ≡ (P (n; i, j, k, ℓ)) n>0 foreahsetofparameters{i, j, k, ℓ}
suhthati+ j = k + ℓ = m
,andto
showthatthemathingnumbersofthepineonesinoursequenesatisfytheorresponding
Gale-Robinson reurrene. More speially, our family of graphs willbe onstruted in
suh away that
• P (n) C is P (n − m)
transplanted to(2, 0)
(that is, shifted two steps to the right),
• P (n) W is P (n − i)
,
• P (n) E is P (n − j)
transplanted to(2, 0)
,
• P (n) N isP (n − k)
transplanted to(1, 1)
, and
• P (n) S isP (n − ℓ)
transplanted to (1, −1)
.
In our onstrution, we use the fat that a losed pineone is ompletely determined by
its set of odd vertial edges, that is, vertial edges of the form
{(a, b), (a, b + 1)}
wherea + b
is odd. We introdue two funtions, an upper funtionU
and a lower funtionL
,whih will be used to determine the positions of the odd vertial edges in the (losed)
pineone
P (n; i, j, k, ℓ)
: forr > 0
,letU (n, r, c) = 2c + r − 3 − 2
mc + kr + i − n − 1 j
,
L(n, r, c) = 2c + r − 3 − 2
mc + ℓr + i − n − 1 j
.
(2)
Observe that the parameters
k
andℓ
play symmetriroles. Also,U (n, 0, c) = L(n, 0, c)
.The funtion
U
will desribe the upper part of the pineone, whileL
will desribe itslower part. Reall that, by onvention, the longest row of a standard pineone is row
0
and its South-West orner liesat oordinates
(0, 0)
, asshown inFigure4.To loate the vertial odd edges in row
r > 0
, alulate the valuesU (n, r, c)
forc = 0, 1, . . .
This will be a (stritly) dereasing sequene, sinem > 2j
(reall thati + j = m
andj 6 i
). Retain those valuesU (n, r, c)
that are larger thanr
, and plae avertialedgeinthe
r
throwatabsissaU (n, r, c)
,thatis,anedgeonneting(U(n, r, c), r)
and
(U(n, r, c), r+1)
(anoddedge,sineU (n, r, c)+r
isodd). Therstrownotontainingsuh an edge (and therefore not inluded in the pineone) is the rst one for whih
U (n, r, 0) < r
. ObservethatU (n, r, 0) − r
isadereasingfuntionofr
(sinej 6 k
). Thispropertyguaranteesthatifthe
r
throwisempty,thenallhigherrowsareemptytoo. Italsoimpliesthattherightmostvertialedgeinrow
r
(whihisloatedatabsissaU (n, r, 0)
)liestotherightoftherightmostvertialedgeinrow
r +1
. (Tosee this,notethatU (n, r, 0)−r
isalwaysanoddnumber.) Sotheinequality
U (n, r + 1, 0) − (r + 1) < U(n, r, 0) −r
impliesU (n, r + 1, 0) − (r + 1) 6 U (n, r, 0) − r − 2
, orU(n, r + 1, 0) < U (n, r, 0)
. That is,the setof odd edges (equivalently, ofblak squares) given by Formula(2) satisesthe top part
ofthe monotoniityonditiondesribedattheend ofSetion2.3: the rightmostoddedge
in row
r > 0
, if itexists, liestothe leftof the rightmostodd edge inrowr − 1
.Similarly, to loate the edges in row
−r 6 0
, alulate the values ofL(n, r, 0) >
L(n, r, 1) > · · ·
and retain those larger thanr
. For eah,plae a vertial edge inrow−r
atabsissa
L(n, r, c)
, that is,onneting(L(n, r, c), −r)
and(L(n, r, c), −r + 1)
. Observethat
L(n, 0, c) = U(n, 0, c)
, so that the olletion of odd vertial edges in row0
is thesame whether it is determinedfrom
U
or fromL
.The monotoniity properties satised by the positions of the odd edges imply that
there exists a unique standard losed pineone whose set of odd vertial edges oinides
withtheset wehaveonstrutedviathefuntions
U
andL
. Toobtainthispineone,drawhorizontaledges from
(r, r + 1)
to(U (n, r, 0), r + 1)
and from(−r, −r)
to(L(n, r, 0), −r)
for all
r > 0
. Finally, plae allthe appropriateeven vertial edges. Sine these steps are so routine, we regard the pineone as fully desribed one the set of odd vertial edgeshas been speied. This pointof view simpliesthe exposition.
Observe that
P (n)
is empty if and only ifU (n, 0, 0) < 0
, whih is equivalent toU (n, 0, 0) 6 −1
(sineU(n, 0, 0)
is odd), whih is easily seen to be equivalent ton < m
(using the fat that
m = i + j
).Example. Take
(i, j, k, ℓ) = (5, 2, 3, 4)
and determineP (12)
. The above denition ofU
and
L
speializestoU (n, r, c) = 2c + r − 3 − 2
7c + 3r − 8 2
, L(n, r, c) = 2c + r − 3 − 2
7c + 4r − 8 2
.
Inrow
0
,wendodd edgeswith lowerverties(5, 0)
and(1, 0)
. Inrow1
,thereisone oddedge at
(4, 1)
. This is the top row of the diagram beauseU(12, 2, 0) = 1 < 2
. Turningto the lower portion of the diagram, there isone odd edge with lower vertex
(2, −1)
andnoneinrow
−2
orbelow. Completingthe diagramisnowroutine,and givesthe pineoneP (12)
whih is shown in Figure10, together with its14 perfet mathings. Aordingly,the Gale-Robinson sequene
a(n)
assoiated with(5, 2, 3, 4)
satisesa(12) = 14
.A larger example ispresented afterCorollary 10.
(2) (4)
(4) (4)
(0, 0)
Figure10: The pineone
P (12; 5, 2, 3, 4)
,with blak squares indiated, and its14 perfetmathings (aross stands for any of the two mathings of asquare).
The pineonesbasedonthe funtions
U
andL
satisfyaremarkableproperty: the oddedges (or, equivalently, the blak squares) in rows
r
andr + 1
are interleaved. That is, between twoblaksquaresinrowr > 0
,thereisablaksquareinrowr + 1
,andsimilarly,between twoblaksquares inrow
r 6 0
, thereisa blak square inrowr − 1
. This anbeheked onthe small example of Figure 10, but is more visibleon the bigger example of
Figure12.
Lemma 6 (The interleaving property) For all values of
n, r
andc
, the funtionsU
and
L
dened by (2) satisfyU (n, r, c + 1) + 1 6 U (n, r + 1, c) 6 U (n, r, c) − 1
and
L(n, r, c + 1) + 1 6 L(n, r + 1, c) 6 L(n, r, c) − 1.
Proof. We have
U (n, r + 1, c) − U (n, r, c + 1) = 2
mc + kr + i − n − 1 + m j
− 2
mc + kr + i − n − 1 + k j
− 1.
But
mc + kr + i − n − 1 + m
j − mc + kr + i − n − 1 + k
j = ℓ
j > 1,
so that the two oors ourring inthe aboveidentity dier by 1 atleast. Consequently,
U (n, r + 1, c) − U (n, r, c + 1) > 2 − 1 = 1.
The three other inequalitiesare proved in asimilar manner.
Wenowwishtoapplytheondensationtheorem(Theorem5)tothepineones
P (n)
wehavejustdened. Usingthe notationofTheorem 5,wewillverifythat,up totranslation,