• 検索結果がありません。

However, their proof did not oer any enumerative interpretation of the Gale-Robinsonnumbers/polynomials

N/A
N/A
Protected

Academic year: 2022

シェア "However, their proof did not oer any enumerative interpretation of the Gale-Robinsonnumbers/polynomials"

Copied!
37
0
0

読み込み中.... (全文を見る)

全文

(1)

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.

(2)

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 the

Somos-

k

reurrene, then one gets a sequene of rational numbers whih for the values

k = 4, 5, 6, 7

is atually a sequene of integers. (Sequenes Somos-4 through Somos-7

are 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

,where

m = i+ j = k +ℓ

. Weall

this 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 integers

i, j, k, ℓ > 0

with

i + j = k + ℓ = m

, the

sequene

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 of

g, h, i, j, k, ℓ, m

, but suh four-term Gale-Robinson reurreneswillnotbeourmain onernhere.

(3)

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 the

n

th graph in the sequene has

a(n)

(perfet)mathings. Ourgraphs,whihweallpineones,generalize thewell-known

Azte 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 a

pineone is shown in Figure1. All pineones are subgraphs of the square grid.

Figure 1: The pineone

P (25; 6, 2, 5, 3)

. Its mathing numberis

a(25)

, where

a(n)

is the

Gale-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, ℓ)

with

n < n

, and a diret method (see

Formula(2)inSetion3)thatallowsonetoonstrutthegraph

P (n; i, j, k, ℓ)

immediately. The heart of our proof is the demonstration that if one denes

a(n)

as the number of

perfet mathings of

P (n) ≡ P (n; i, j, k, ℓ)

, the sequene

a(0), a(1), a(2), ...

satises the

Gale-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 that

P (n)

has

a(n)

perfetmathingsforall

n

,whihyieldsadditionallytheintegralityof

a(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

and

p(0) = p(1) = · · · = p(m − 1) = 1

,isasequene ofpolynomials in

w

and

z

withnonnegative integeroeients. More preisely, weprove inTheorem 20 that

p(n; u 2 , v 2 )

ountsperfet mathings ofthe pineone

P (n; i, j, k, ℓ)

by the numberof

(4)

speial horizontaledges(theexponentof the variable

u

)and the numberofvertialedges

(the exponent of the variable

v

). The fat that

p(n)

is a polynomial with oeients in

Z

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 quantity

A(n, p, q)

satisfyingthe

perturbed 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,

(5)

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

,therationalfuntions

A(n, p, q)

and

A(n, r, s)

arethesamefuntion

up to re-indexing of the indeterminates.

Propponjeturedthateah

A(n, p, q)

isaLaurentpolynomialinsome nitesubsetof

the(innitelymany)indeterminates

x n,r,s

,withintegeroeients;thatis,eah

A(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 numbers

a(n)

. Propp onjetured that eah

oeientineahsuhLaurentpolynomialispositive(afatthatisnot proved byFomin

and Zelevinsky's method)and furthermore is equal to

1

.

Proppknewthatinthease

i = j = k = ℓ = 1

,the Laurentpolynomials

A(n, p, q)

an

beinterpretedasmultivariatemathingpolynomialsofsuitablegraphs,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. This

artileled 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 for

small 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℄.

(6)

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 an

orderedpair

(V, E )

where

V

isanitesetofverties,and

E

,thesetofedges,isaolletion

of2-elementsubsetsof

V

. Thedegreeofavertex

v

isthenumberofedgesin

E

ontaining

v

. Asubgraphof

G

isagraph

H = (V , E )

suhthat

V ⊂ V

and

E ⊂ E

. If,inaddition,

V = V

, we say that

H

is a spanning subgraph of

G

. The intersetion of two graphs

G = (V, E)

and

H = (V , E )

is the graph

G ∩ H = (V ∩ V , E ∩ E )

, and the union of

the two graphsisthe graph

G ∪ H = (V ∪ V , E ∪ E )

. Given twographs

G = (V, E)

and

H = (V , E )

, we denoteby

G \ H

the subgraph

(V ′′ , E ′′ )

, where

V ′′ = V \ V

and

E ′′

is

the set of edges of

E \ E

havingboth endpoints in

V ′′

.

A perfet mathing of agraph

G = (V, E)

is a subset

E

of

E

suh that every vertex

of

V

belongs to exatly one edge of

E

. We willsometimes omit the word perfet and

refertoperfet mathings assimplymathings. The mathingnumber of

G

,denoted by

m(G)

, is the number of perfet mathings of

G

. More generally, we shall often onsider

the set

E

of edges as a set of ommuting indeterminates, and assoiate with a (perfet) mathing

E

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

and

y

if

{x, y}

isnot in

E

). In partiular, if eah

n e

is set equal to0or 1,then

the mathingpolynomial beomesthe numberof perfet mathingsof the subgraph of

G

onsisting of preisely those edges

e

for whih

n 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 length

1, 3, . . . , 2k − 3, 2k − 1, 2k −3, . . . , 3, 1

andstakingthemfromtoptobottom,withthemiddlesquaresinallthe

rows lining up vertially, asillustrated by Figure 2. Let

A

be a diamondgraph of width

(7)

9

e

s n

w

Figure 2: An Azte diamondgraph of width

9

,and one of itsperfet mathings.

2k − 1

. Let

A 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 remaining

2k − 3

olumns of

A

. We all

A N

the North sub-diamond of

A

. Dene similarly the

South, West and East sub-diamonds of

A

, denoted by

A S , A W

and

A E

. Finally, let

A C

be the entral sub-diamond of

A

of width

2k − 5

(Figure 3). The following result is a

reformulationof 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-diamondsby

M(A)M (A C ) = nsM (A W )M (A E ) + ewM (A N )M (A S ),

where

n, s, w,

and

e

denote respetively thetop (resp. bottom, westmost,eastmost)edge of

A

(see Figure 2).

In partiular, if

a(n)

(with

n > 2

) denotes the mathing number of a diamond graph of

width

2n − 3

,then

a(n)a(n − 2) = 2a(n − 1) 2

for all

n > 2

, provided we adopt the initialonditions

a(0) = a(1) = 1

. This shows that

a(n)

is the three-term Gale-Robinson sequene assoiated with

i = j = k = ℓ = 1

, and

implies

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,andlet

G

beaspanningsubgraphof

A

,ontaining

the edges

n, s, w

and

e

. Let

G N = G ∩ A N

, and dene

G S , G W , G E

and

G C

similarly.

Then

M (G)M(G C ) = nsM(G W )M (G E ) + ewM (G N )M (G S ).

(8)

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 of

A

, every perfet mathing of

G

is a perfet

mathing of

A

. Hene the mathing polynomial

M (G)

is simply obtained by setting

a = 0

in

M (A)

, for every edge

a

that belongs to

A

but not to

G

. The same property

relates

M (G N )

and

M (A N )

, and so on. Consequently, Corollary 2 issimplyobtained by setting

a = 0

in Theorem 1,for every edge

a

that belongsto

A

but not to

G

.

2.3 Pineones: denitions

A standard pineone of width

2k − 1

is a subgraph

P = (V, E)

of the square lattie

satisfyingthe three following onditions,illustrated by Figure4.

a

:

1.

Thehorizontaledges form

i + j + 1

segmentsof oddlength, startingfromthepoints

(0, 1), (1, 2) . . . , (i − 1, i)

and

(0, 0), (1, −1), . . . , (j, −j)

,forsome

i > 1

,

j > 0

. More-

over, if

L m

denotes the length of the segment lyingat ordinate

m

, then

L − j < · · · < L − 1 < L 0 = 2k − 1 = L 1 > L 2 > · · · > L i .

2.

The set of verties

V

is the set of verties of the square lattiethat are inident to

the above horizontaledges.

(9)

3.

Let

e = {(a, b), (a, b + 1)}

beavertialedgeofthesquare lattiejoiningtwoverties

of

V

. If

a + b

is even, then

e

belongs tothe set ofedges

E

, and we say that

e

is an

even edgeof

P

. Otherwise,

e

may belong to

E

,or not (Figure4.

a

), and we all

e

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)

, where

a + b

is

even. 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, or

not.

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 it

ontains no vertex of degree

1

. (Suh a vertex an only our at the right border of the

pineone, 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 of

a 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. The

faesofthe 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 width

2k − 1

ontainsexatly

2k − 1

ells, butmayontainnosquareatall. Denotingby

(resp.

r

)the

leftmost (resp. rightmost) ell of the longest row of

P

, we say that

P

is rooted on

(ℓ, r)

.

(If

P

is standard, then

is the ell with

(0, 0)

as its lower-left orner.) We refer to the

longest row of a pineone as row

0

. The row above it (resp. below) is row

1

(resp.

−1

),

and so on.

It is easy tosee that a pineone

P

is losed if and onlyif the rightmost nite fae of

eahrowisablak square. In thisase,the rightmostblaksquareineahrowisalsothe

rightmost ell of the row. If moreover

P

is standard, it is ompletelydetermined by the

position of itsblak squares. Equivalently,it isompletely determinedby the positionof

(10)

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 one

squareof

S

areonseutive(sayfromrow

−j

torow

i

, whererow

m

referstoellsloated

between ordinates

m

and

m + 1

)andfor

m > 0

(resp.

m < 0

),the rightmostblaksquare

inrow

m

ourstothe leftoftherightmostblaksquare inrow

m − 1

(resp.

m + 1

). Then

is 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 of

P

annot belong to any perfet

mathingof

P

. Speially,if

v

isavertex ofdegree1 in

P

,theninany perfet mathing

of

P

,

v

must be mathed with the vertex to its left (all it

u

), so that

u

annot be

mathed 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 righthalf

of thepitureshows a losedsub-pineone

P ¯

of

P

alongwith aset of isolatededges. The

reader 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 ontained

in every perfet mathing of

P

), so that a perfet mathing of

P

is nothing other than

a perfet mathing of

P ¯

together with the set of isolated edges shown at right. In this

subsetion, we will give a systemati way of reduing a pineone

P

to a smaller losed

pineone by pruning away some fored and forbidden edges.

Figure5: From apineone

P

to itsore

P ¯

.

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 a

largest losed standard sub-pineone of

P

, namely, the union of all the losed standard

sub-pineones of

P

. Weallthisthe ore of

P

anddenoteitby

P ¯

. (If

P

isnotastandard

pineone but a transplanted pineone rooted at the ell with lower-left orner

(a, b)

, we

(11)

dene

P 0

asthe standard pineone obtained by translating

P

by

(−a, −b)

, and we dene

the ore of

P

asthe ore of

P 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. Let

b 0

be the rightmost blak square in row 0 of

P

, let

b 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

all the faes of

P

that lie in the same row as,and lieweakly tothe left of, one of one of

the

b k

's. Thisset offaesgivesalosedpineone

P ˜

. Atthe sametime,itislearthatany

losedsub-pineone

Q

of

P

must beasub-pineone of

P ˜

. For,the rightmostblaksquare

in row 0 of

Q

an be no farther to the right than

b 0

, whih implies that the rightmost

blak square in row 1 of

Q

an be no farther to the right than

b 1

, et.; and likewise for

the bottom half of

Q

. Hene the sub-pineone

P ˜

we haveonstruted is none otherthan

the ore of

P

as dened above.

If

P

is losed, then

P ¯ = 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 ore

P ¯

. There is a unique perfet mathing of

P \ P ¯

onsisting exlusively of horizontal edges (see Figure 5); let

H

be the edge set of this

perfet mathing. Every perfet mathing of

P ¯

an be extended to a perfet mathing

of

P

by adjoining the edges in

H

, so

m(P ) > m( ¯ P )

. We now show that every perfet

mathing of

P

is obtained froma perfet mathing of

P ¯

inthis way.

Proposition 3 Let

P

be a pineone with ore

P ¯

. Then

m( ¯ P ) = m(P )

.

Proof. Wewillprovethis laim by usinga proedure that redues asub-pineone

Q

of

P

toasmallersub-pineone with thesamemathingnumber. Let

Q

beasub-pineoneof

P

whoseore oinides with

P ¯

. If

Q

isnot losed,then theremust beatleast onevertex of

degree1alongtherightboundaryof

Q

. Let

v = (a, b)

beoneofthetherightmostverties

of degree

1

in

Q

. Then

v

isthe rightmost vertex inone of the rows of

Q

. Assume for the

(12)

moment that

v

lies stritly above the longestrowof

Q

(that is,

b > 1

). See the top part

of Figure7 for anillustration of the following argument. Let

u

be the vertex to the left

of

v

. Then the edge joining

u

and

v

is fored to belong to every perfet mathing of

Q

,

while every other edge ontaining

u

is forbiddenfrom belongingto any perfet mathing

of

Q

. Hene thegraph

Q

obtained from

Q

bydeleting

u

,

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 to

Q

. In this ase,

v 1

has degree 1 in

Q

. Let

i

be the

largest integer suh that

v j = (a − j, b + j)

belongs to

Q

for all

0 6 j 6 i

. Applying the

deletion 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 of

Q

of the

form

(a − j, 1 + j)

or

(a − j, −j )

yields again a pineone

Q

(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,weanhekthattheoreof

Q

is

P ¯

. The

onlythingwemightworryabout isthatinpassingfrom

Q

to

Q

,weremoved someedges

that belong to

P ¯

. The examination of Figure5 shows that we would have, inpartiular, removed the rightmost vertial edge is some row of

P ¯

. 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 )

,take

Q = P

and use the preedingoperationrepeatedly

toonstrut 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-

pineone of

P

whose ore is

P ¯

; that is, we arrive at

P ¯

itself. And sine eah step of our

onstrution preserves

m(Q)

,weonlude that

m( ¯ P ) = m(P )

,as laimed.

(13)

Let

P

be a losed pineone, with longest row onsisting of

2n + 1

squares. Let

A

be the

smallestdiamondgraphontaining

P

(thelongestrowof

A

ontains exatly

2n + 1

ells).

Let

G

denote the spanning subgraph of

A

whose edge-set onsists of all edges of

P

, all

horizontal edges of

A

, and all even vertial edges of

A

(Figure 8). Observe that

G

is a

pineone. Moreover, amongthe spanning subgraphs of

A

that are pineones and ontain

P

,

G

has stritly fewer edges than the others. Sine no odd vertial edge is added,

P

is

atually 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

and

G C

are (standardortransplanted)pineones. Let

P N

,

P S

,

P W

,

P E

and

P C

denote theirrespetiveores. (These are nottobeonfusedwith

P N

,et., whih

are theintersetionsof

P

with

A N

,et.) Wewilloftenall

P N

,

P S

,

P W

,

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

row just above (resp. below)

R 0

. Observe that the ells

r 0 , r 1

and

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

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 is

r 1

(resp.

r − 1

). Similarly,

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 )

.

This propositionimplies that apineone

P

that isneither empty, nor redued to ablak

square an be reonstruted from its four main sub-pineones

P N

,

P S

,

P E

and

P W

.

Indeed, thepart of

P

loatedstritlyabove itslongestrowoinides with the top partof

(14)

P 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

, row

r

of

P

oinides with row

r + 1

of

P S

. It thus remains to determine the

longest row of

P

. This row is obtained by adding a

2

-by-

1

retangle2 to the left of the

longest rowof

P E

,and thensuperimposing the longest rowof

P W

.

LetusnowapplyCorollary2tothegraph

G

obtainedbyompleting

P

intoaspanning

pineone of

A

(Figure8). ByProposition3, sine

P

isthe ore of

G

,

m(G) = m(P )

,and

similar 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 by

m(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

isthe

n

thterminthe

2

Thisretangleisatuallyonlyusefulif

P W

isemptyorreduedtoasingleblaksquare.

(15)

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 form

a(n)a(n − m) = a(n − i)a(n − j) + a(n − k)a(n − ℓ),

(1)

with initial onditions

a(n) = 1

for

n = 0, 1, . . . , m − 1

. Here,

i, j, k

and

are positive

integers suhthat

i + j = k + ℓ = m

, and weadopt the following(important)onvention

j = min{i, j, k, ℓ}.

Ourpurposeinthissetionistoonstrutasequeneof(losed)pineones

(P (n)) n> 0 ≡ (P (n; i, j, k, ℓ)) n>0

foreahsetofparameters

{i, j, k, ℓ}

suhthat

i+ 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

is

P (n − k)

transplanted to

(1, 1)

, and

• P (n) S

is

P (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)}

where

a + b

is odd. We introdue two funtions, an upper funtion

U

and a lower funtion

L

,

whih will be used to determine the positions of the odd vertial edges in the (losed)

pineone

P (n; i, j, k, ℓ)

: for

r > 0

,let

U (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, while

L

will desribe its

lower 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 values

U (n, r, c)

for

c = 0, 1, . . .

This will be a (stritly) dereasing sequene, sine

m > 2j

(reall that

(16)

i + j = m

and

j 6 i

). Retain those values

U (n, r, c)

that are larger than

r

, and plae a

vertialedgeinthe

r

throwatabsissa

U (n, r, c)

,thatis,anedgeonneting

(U(n, r, c), r)

and

(U(n, r, c), r+1)

(anoddedge,sine

U (n, r, c)+r

isodd). Therstrownotontaining

suh an edge (and therefore not inluded in the pineone) is the rst one for whih

U (n, r, 0) < r

. Observethat

U (n, r, 0) − r

isadereasingfuntionof

r

(sine

j 6 k

). This

propertyguaranteesthatifthe

r

throwisempty,thenallhigherrowsareemptytoo. Italso

impliesthattherightmostvertialedgeinrow

r

(whihisloatedatabsissa

U (n, r, 0)

)lies

totherightoftherightmostvertialedgeinrow

r +1

. (Tosee this,notethat

U (n, r, 0)−r

isalwaysanoddnumber.) Sotheinequality

U (n, r + 1, 0) − (r + 1) < U(n, r, 0) −r

implies

U (n, r + 1, 0) − (r + 1) 6 U (n, r, 0) − r − 2

, or

U(n, r + 1, 0) < U (n, r, 0)

. That is,the set

of 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 inrow

r − 1

.

Similarly, to loate the edges in row

−r 6 0

, alulate the values of

L(n, r, 0) >

L(n, r, 1) > · · ·

and retain those larger than

r

. 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)

. Observe

that

L(n, 0, c) = U(n, 0, c)

, so that the olletion of odd vertial edges in row

0

is the

same whether it is determinedfrom

U

or from

L

.

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

and

L

. Toobtainthispineone,draw

horizontaledges 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 edges

has been speied. This pointof view simpliesthe exposition.

Observe that

P (n)

is empty if and only if

U (n, 0, 0) < 0

, whih is equivalent to

U (n, 0, 0) 6 −1

(sine

U(n, 0, 0)

is odd), whih is easily seen to be equivalent to

n < m

(using the fat that

m = i + j

).

Example. Take

(i, j, k, ℓ) = (5, 2, 3, 4)

and determine

P (12)

. The above denition of

U

and

L

speializesto

U (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)

. Inrow

1

,thereisone odd

edge at

(4, 1)

. This is the top row of the diagram beause

U(12, 2, 0) = 1 < 2

. Turning

to the lower portion of the diagram, there isone odd edge with lower vertex

(2, −1)

and

noneinrow

−2

orbelow. Completingthe diagramisnowroutine,and givesthe pineone

P (12)

whih is shown in Figure10, together with its14 perfet mathings. Aordingly,

the Gale-Robinson sequene

a(n)

assoiated with

(5, 2, 3, 4)

satises

a(12) = 14

.

A larger example ispresented afterCorollary 10.

(17)

(2) (4)

(4) (4)

(0, 0)

Figure10: The pineone

P (12; 5, 2, 3, 4)

,with blak squares indiated, and its14 perfet

mathings (aross stands for any of the two mathings of asquare).

The pineonesbasedonthe funtions

U

and

L

satisfyaremarkableproperty: the odd

edges (or, equivalently, the blak squares) in rows

r

and

r + 1

are interleaved. That is, between twoblaksquaresinrow

r > 0

,thereisablaksquareinrow

r + 1

,andsimilarly,

between twoblaksquares inrow

r 6 0

, thereisa blak square inrow

r − 1

. This anbe

heked 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

and

c

, the funtions

U

and

L

dened by (2) satisfy

U (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)

we

havejustdened. Usingthe notationofTheorem 5,wewillverifythat,up totranslation,

P (n) W = P (n − i)

,

P (n) E = P (n − j)

,

P (n) N = P (n − k)

,

P (n) S = P (n − ℓ)

and

P (n) C = P (n − m)

. Theseequivaleneswillfollowfromthe interleavingproperty andthe followingalgebraiequalities.

参照

関連したドキュメント

This means that finding the feasible arrays for distance-regular graphs of valency 4 was reduced to a finite amount of work, but the diameter bounds obtained were not small enough

Many interesting graphs are obtained from combining pairs (or more) of graphs or operating on a single graph in some way. We now discuss a number of operations which are used

Perhaps the most significant result describing planar graphs as intersection graphs of curves is the recent proof of Scheinerman’s conjecture that all planar graphs are segment

In our paper we tried to characterize the automorphism group of all integral circulant graphs based on the idea that for some divisors d | n the classes modulo d permute under

For example, a maximal embedded collection of tori in an irreducible manifold is complete as each of the component manifolds is indecomposable (any additional surface would have to

It is suggested by our method that most of the quadratic algebras for all St¨ ackel equivalence classes of 3D second order quantum superintegrable systems on conformally flat

[3] Chen Guowang and L¨ u Shengguan, Initial boundary value problem for three dimensional Ginzburg-Landau model equation in population problems, (Chi- nese) Acta Mathematicae

As a consequence of this characterization, we get a characterization of the convex ideal hyperbolic polyhedra associated to a compact surface with genus greater than one (Corollary