RANDOM PLANAR LATTICES AND INTEGRATED SUPERBROWNIAN EXCURSION

-

Documents
45 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur, Doctorat, Bac+8
RANDOM PLANAR LATTICES AND INTEGRATED SUPERBROWNIAN EXCURSION PHILIPPE CHASSAING AND GILLES SCHAEFFER Abstract. In this paper, a surprising connection is described between a spe- cific brand of random lattices, namely planar quadrangulations, and Aldous' Integrated SuperBrownian Excursion (ISE). As a consequence, the radius rn of a random quadrangulation with n faces is shown to converge, up to scaling, to the width r = R?L of the support of the one-dimensional ISE, or precisely: n?1/4rn law?? (8/9)1/4 r. More generally the distribution of distances to a random vertex in a random quadrangulation is described in its scaled limit by the random measure ISE shifted to set the minimum of its support in zero. The first combinatorial ingredient is an encoding of quadrangulations by trees embedded in the positive half-line, reminiscent of Cori and Vauquelin's well labelled trees. The second step relates these trees to embedded (discrete) trees in the sense of Aldous, via the conjugation of tree principle, an analogue for trees of Vervaat's construction of the Brownian excursion from the bridge. From probability theory, we need a new result of independent interest: the weak convergence of the encoding of a random embedded plane tree by two contour walks (e(n), W (n)) to the Brownian snake description (e, W ) of ISE.

  • random planar

  • random quadrangulations

  • continuum limit

  • freely embedded trees

  • qn-valued random variable

  • discrete trees

  • trees

  • aldous' prescription

  • let ln


Sujets

Informations

Publié par
Nombre de lectures 8
Langue English
Signaler un problème

RANDOMPLANARLATTICESANDINTEGRATED
SUPERBROWNIANEXCURSION

PHILIPPECHASSAINGANDGILLESSCHAEFFER

Abstract.
Inthispaper,asurprisingconnectionisdescribedbetweenaspe-
cificbrandofrandomlattices,namelyplanarquadrangulations,andAldous’
IntegratedSuperBrownianExcursion(ISE).Asaconsequence,theradius
r
n
ofarandomquadrangulationwith
n
facesisshowntoconverge,uptoscaling,
tothewidth
r
=
R

L
ofthesupportoftheone-dimensionalISE,orprecisely:
n

1
/
4
r
n
l

aw

(8
/
9)
1
/
4
r.
Moregenerallythedistributionofdistancestoarandomvertexinarandom
quadrangulationisdescribedinitsscaledlimitbytherandommeasureISE
shiftedtosettheminimumofitssupportinzero.
Thefirstcombinatorialingredientisanencodingofquadrangulationsby
treesembeddedinthepositivehalf-line
,reminiscentofCoriandVauquelin’s
welllabelledtrees.Thesecondsteprelatesthesetreestoembedded(discrete)
treesinthesenseofAldous,viathe
conjugationoftreeprinciple
,ananalogue
fortreesofVervaat’sconstructionoftheBrownianexcursionfromthebridge.
Fromprobabilitytheory,weneedanewresultofindependentinterest:the
weakconvergenceoftheencodingofarandomembeddedplanetreebytwo
contourwalks(
e
(
n
)
,W
ˆ
(
n
)
)totheBrowniansnakedescription(
e,W
ˆ)ofISE.
Ourresultssuggesttheexistenceofa
ContinuumRandomMap
describing
intermofISEthescaledlimitofthedynamicaltriangulationsconsideredin
two-dimensionalpurequantumgravity.

1.
Introduction
Fromadistantperspective,thisarticleuncoversasurprising,andhopefullydeep,
relationbetweentwofamousmodels:
randomplanarmaps
,asstudiedincombina-
toricsandquantumphysics,and
Browniansnakes
,asstudiedinprobabilitytheory
andstatisticalphysics.Moreprecisely,ourresultsconnectsomedistance-related
functionalsof
randomquadrangulations
withfunctionalsofAldous’
IntegratedSu-
perBrownianExcursion
(ISE)indimensionone.
Quadrangulations.
Ontheonehand,quadrangulationsarefiniteplanegraphs
with4-regularfaces(seeFigure1andSection2forprecisedefinitions).Random
quadrangulations,likerandomtriangulations,randompolyhedra,orthe
φ
4
-models
ofphysics,areinstancesofageneralfamilyofrandomlatticesthathasreceived
considerableattentionbothincombinatorics(underthename
randomplanarmaps
,
followingTutte’sterminology[35])andinphysics(underthename
Euclideantwo-
dimensionaldiscretisedquantumgeometry
,orsimply
dynamicaltriangulations
or
fluidlattices
[3,10,18]).
Manyprobabilisticpropertiesofrandomplanarmapshavebeenstudied,that
are
localproperties
likevertexorfacedegrees[7,17],or0

1lawsforproperties
expressibleinfirstorderlogic[8].Otherwelldocumentedfamiliesofpropertiesare
relatedtoconnectednessandconstantsizeseparators[6],alsoknownasbranchings
1

2

CHASSAINGANDSCHAEFFER

Figure1.
Randomquadrangulations,inplanarorsphericalrepresentation.
intobabyuniverses[21].Inthisarticleweconsideranotherfundamentalaspectof
thegeometryofrandommaps,namely
globalpropertiesofdistances
.The
profile
(
H
kn
)
k

0
and
radius
r
n
ofarandomquadrangulationwith
n
facesaredefinedin
analogywiththeclassicalprofileandheightoftrees:
H
kn
isthenumberofverticesat
distance
k
fromabasepoint,while
r
n
isthemaximaldistancereached.Ithadbeen
acceptedinphysicssincethe80’sthatforsuchdiscretegeometries
theinternal
Hausdorffdimensionis4
,butexactcomputationsabouttheprofile(withtrian-
gulationsinsteadofquadrangulations)werefirstobtainedbyphysicistsWatabiki,
Ambjørnet
al.
(see[4,36]andref.therein).Understrong(unproven)smoothness
assumptionsonthebehavioroftheprofile,theyobtainthattheonlypossiblescal-
ingisindeed
k

n
1
/
4
,andtheycomputeatransformoftheprofileinthescaling
limit
1
.Althoughnonrigourous(duetoapproximationsandlimitsinterchanges),
theseresultsareremarkablypreciseandbeautifullyderived.Independentlythe
conjecturethat
E
(
r
n
)

cn
1
/
4
wasproposedbySchaeffer[31].
IntegratedSuperBrownianExcursion.
Ontheotherhand,ISEwasintroduced
byAldousasamodelofrandomdistributionsofmasses[1].Heconsidersrandom
embeddeddiscretetreesasobtainedbythefollowingtwosteps:firstanabstract
tree
t
,sayaCayleytreewith
n
nodes,istakenfromtheuniformdistributionand
eachedgeof
t
isgivenlength1;then
t
isembeddedintheregularlatticeon
Z
d
,
withtherootattheorigin,andedgesofthetreerandomlymappedonedgesofthe
lattice.Assigningmassestoleavesofthetree
t
yieldsarandomdistributionofmass
on
Z
d
.Uponscalingthelatticeto
n

1
/
4
Z
d
,theserandomdistributionsofmass
admit,for
n
goingtoinfinity,acontinuumlimit
J
whichisarandomprobability
measureon
R
d
calledISE.
DerbezandSladeprovedthatISEdescribesindimensionlargerthan8the
continuumlimitofamodeloflatticetrees[16],whileHaraandSladeobtainedthe
samelimitfortheincipientinfiniteclusterinpercolationindimensionlargerthan
6[19].Asopposedtotheseworks,weshallconsiderISEindimensiononeandour
embeddeddiscretetreesshouldbethoughtofasfoldedonaline.Thesupportof
ISEisthenarandominterval(
L,R
)of
R
thatcontainstheorigin.
FromquadrangulationstoISE.
Thepurposeofthispaperistodrawarela-
tionbetween,ontheonehand,randomquadrangulations,and,ontheotherhand,
1
Morepreciselytheyobtainthatthesingularbehaviorofthefunction

n

k
H
k
(
n
)
z
n
nearits
dominantsingularity
z
0
is
ct
3
/
4
cosh(
t
1
/
4
k
)
/
sinh(
t
1
/
4
k
)with
c,c

constantsand
t
=
c

(1

z/z
0
).

ERANDOMMAPSANDISE3
Aldous’ISE:uponproperscaling,theprofileofarandomquadrangulationsisde-
scribedinthelimitbyISEtranslatedtohavesupport(0
,R

L
).Thisrelation
impliesinparticularthattheradius
r
n
ofrandomquadrangulations,againupon
scaling,weaklyconvergestothewidthofthesupportofISEinonedimension,that
isthecontinuousrandomvariable
r
=
R

L
.Weshallindeedprove(Corollary3)
tahtn

1
/
4
r
n
l

a

w
(8
/
9)
1
/
4
r,
aswellastheconvergenceofmoments.Thisprovestheconjecture
E
(
r
n
)

cn
1
/
4
.
Inthefirstversionofthispaper,thevalueoftheconstant
c
wasquotedasunknown.
Inthemeantime,Delmas[14]hascomputedamomentgeneratingfunctionof
R
andthefirstandsecondmomentof
r
,givinginparticular
2
3
/
4
Γ(5
/
4)
(
r
)=6

.
πWeshallmoregenerallyprove(Corollary4)thatthenormalizedcumulatedpro-
file,thatisthefractionofthenumberofverticesatdistanceatmost
xn
1
/
4
ofthe
basepoint,convergestothefractionofthemassoftheISEintheinterval(0
,x
),
whenISEisshiftedtohavesupport(0
,R

L
).
ThepathfromquadrangulationstoISEconsistsofthreemainsteps,thefirsttwo
ofcombinatorialnatureandthelastwithamoreprobabilisticflavor.Ourfirststep,
Theorem1,revisitsacorrespondenceofCoriandVauquelin[13]betweenplanar
mapsandsome
welllabelledtrees
,thatcanbeviewedasplanetreesembeddedin
thepositivehalf-line.Thankstoanalternativeconstruction[31,Ch.7],weshow
thatunderthiscorrespondencetheprofilecanbemappedtothemassdistribution
onthehalf-line.Inparticular,theradius
r
n
ofarandomquadrangulationisequal
inlawtothemaximallabel
µ
n
ofarandomwelllabelledtree.
Safeforthepositivitycondition,welllabelledtreeswouldbeconstructedexactly
accordingtoAldous’prescriptionforembeddeddiscretetrees.Welllabelledtrees
arethustoAldous’embeddedtreeswhattheBrownianexcursionistotheBrownian
bridge,andweseekananalogueofVervaat’srelation.Atthediscretelevela
classicalelegantexplanationofsuchrelationsisbasedonDvoretskyandMotzkin’s
cyclicshiftsandcyclelemma(seealsoOtter).Oursecondcombinatorialstep,
Theorem3,consistsintheadaptationoftheseideastoembeddedtrees.More
precisely,viathe
conjugationoftreeprinciple
of[31,Chap.2],weboundthe
discrepancybetweenthemassdistributionofourconditionedtreesonthepositive
half-lineandatranslatedmassdistributionoffreelyembeddedtrees.Inparticular
weconstructacouplingbetweenwelllabelledtreesandfreelyembeddedtreessuch
thatthelargestlabel
µ
n
,andthustheradius
r
n
,iscoupledtothewidthofthe
support(
L
n
,R
n
)ofrandomfreelyembeddedtrees:
|
r
n

(
R
n

L
n
)
|≤
3
.
Wealsosketchanalternativeconstruction,directlyrelatingfreelyembeddedtrees
toquadrangulations.Sinceourfreelyembeddedtreesareconstructedaccordingto
Aldous’prescription,onecouldexpecttobeabletoconcludedirectly.Howevertwo
obstaclesstillneedtobebypassedatthispoint.

4CHASSAINGANDSCHAEFFER
ContourwalksandBrowniansnakes.
Thefirstobstacleisthattheconstruc-
tionofISEasacontinuumlimitofmassdistributionssupportedbyembedded
discretetreeswasonlyoutlinedinAldous’originalpaper.Theoriginalmathemat-
icaldefinitionisbyembeddingacontinuumrandomtree(CRT),whichamountsto
exchangingtheembeddingandthecontinuumlimit.ButBorgset
al.
provedthat
indeedISEisthelimitofmassdistributionssupportedbyembeddedCayleytrees
[12]andtheirproofcouldcertainlybeadaptedtoothersimpleclassesoftreesand
inparticulartoourembeddedplanetrees.
Thesecond,moreimportant,obstacleisthatweakconvergenceofprobability
measuresisnotadequatetoourpurpose,sinceweareinterestedinparticularin
convergenceofthewidthofthesupport,
whichisnotacontinuousfunctionalonthe
spaceofmeasures
.Inordertocircumventthisdifficulty,weturntothedescription
ofISEintermsofsuperprocesses:ISEcanbeconstructedfromtheBrowniansnake
withlifetime
e
,thestandardBrownianexcursion[1,23].
Fromthediscretepointofview,weconsidertheencodingofanembeddedplane
treebyapairofcontourwalks(
x
k
,y
k
),thatencoderespectivelytheheightofthe
nodevisitedattime
k
anditspositionontheline.Ourlastresult,Theorem5,is
theweakconvergence,uponproperscaling,ofthispairofwalkstotheBrownian
snakewithlifetime
e
:
e
(
n
)
(
s
)
,W
ˆ
(
n
)
(
s
)
l

a

w
e
(
s
)
,W
ˆ
s
.
As
R
=sup
s
W
ˆ
s
and
L
=inf
s
W
ˆ
s
thisconvergence,togetherwithsomedeviation
boundsobtainedintheproofallowsustoconcludeontheradius.(Asimilarweak
convergencewasindependentlyprovedbyMarckertandMokkadem[26]butwithout
thedeviationboundsweneedhere.)
Moregenerallythejointconvergenceoftheminimumandthemassdistribution
ofdiscreteembeddedtreesimpliesthat,uponscaling,thelabeldistributionofwell
labelledtreesconvergestoISEtranslatedtohavetheminimumofitssupportat
theorigin.Thesamethenholdsfortheprofileofrandomquadrangulations.
DynamicaltriangulationsandaContinuumRandomMap.
Althoughwe
concentrateinthisarticleontheradiusandprofileofrandomquadrangulations,
ourderivationsuggestsamuchtighterlinkbetweenrandomquadrangulationsand
ISE.WeconjecturethataContinuumRandomMap(CRM)canbebuiltfromISE
thatwoulddescribethecontinuumlimitofscaledrandomquadrangulations,ina
similarwayastheCRTdescribesthecontinuumlimitofscaledrandomdiscrete
trees.Fromthepointofviewofphysics,theresultingCRMwoulddescribein
thelimitthegeometryofscaleddynamicaltriangulationsasstudiedindiscretised
two-dimensionalEuclideanpurequantumgeometries[3,10,18].Weplantodiscuss
thisconnectionfurtherinfuturework.
Organizationofthepaper.
Section2containsthedefinitionofthecombinatorial
modelsofrandomlattices.Sections3and4aredevotedtothefirstcombinatorial
steps.Section5containsthedefinitionofprobabilisticmodels,andthestatement
oftheconvergenceresult.FinallyinSection6wegivetheproofofthisconvergence.
2.
Thecombinatorialmodelsofrandomlattices
2.1.
Planarmapsandquadrangulations.
A
planarmap
isaproperembedding
(withoutedgecrossings)ofaconnectedgraphintheplane.Loopsandmultiple

RANDOMMAPSANDISE

Figure2.
Twodistinctplanarmaps,andasphericalrepresenta-
tionofthesecond.

5

edgesare
apriori
allowed.Aplanarmapis
rooted
ifthereisa
root
,
i.e.
adistin-
guishededgeontheborderoftheinfiniteface,whichisorientedcounterclockwise.
Theoriginoftherootiscalledthe
rootvertex
.Tworootedplanarmapsareconsid-
eredidenticalifthereexistsanhomeomorphism
oftheplane
thatsendsonemap
ontotheother(rootsincluded).
Thedifferencebetweenplanargraphsandplanarmapsisthatthecyclicorder
ofedgesaroundverticesmattersinmaps,asillustratedbyFigure2.Observe
thatplanarmapscanbeequivalentlydefinedonthesphere.InparticularEuler’s
characteristicformulaappliesandprovidesarelationbetweenthenumbers
n
of
edges,
f
offacesand
v
ofverticesofanyplanarmap:
f
+
v
=
n
+2.
The
degree
ofafaceorofavertexofamapisitsnumberofincidenceofedges.
Aplanarmapisa
quadrangulation
ifallfaceshavedegree4.All(planar)quadran-
gulationsare
bipartite
:theirverticescanbecoloredinblackorwhitesothatthe
rootiswhiteandanyedgejoinstwoverticeswithdifferentcolors.Inparticulara
quadrangulationcontainsnoloopbutmaycontainmultipleedges.SeeFigures1
and3forexamplesofquadrangulations.
Let
Q
n
denotethesetofrootedquadrangulationswith
n
faces.Aquadrangula-
tionwith
n
faceshas2
n
edges(becauseofthedegreeconstraint)and
n
+2vertices
(applyingEuler’sformula).Thenumberofrootedquadrangulationswith
n
faces
wasobtainedbyW.T.Tutte[35]:
23
n

2
n

(1)
|Q
n
|
=
n
+2
n
+1
n.
Variousalternativeproofsofthisresulthavebeenobtained(see
e.g.
[5,10,13,31]).
Ourtreatmentwillindirectlyprovideanotherproof,relatedto[13,31].
2.2.
Randomplanarlattices.
Let
L
n
bearandomvariablewithuniformdis-
tributionon
Q
n
.Formally,
L
n
isthe
Q
n
-valuedrandomvariablesuchthatforall
QnQ∈11Pr(
L
n
=
Q
)=
|Q|
=
23
n

2
n

.
nn
+2
n
+1
n
Therandomvariable
L
n
isour
randomplanarlattice
.Toexplainthisterminol-
ogy,takenfromphysics,observethatlocallytheusualplanarsquarelatticeisa
planarmapwhosefacesandverticesallhavedegree4.Ourrandomplanarlattice
correspondstoarelaxationoftheconstraintonvertices.

6

CHASSAINGANDSCHAEFFER
e1e+1e+1
31221
e+2
2e21
e+1e+1
e0Figure3.
Labellingbydistancefromtherootvertexandthetwo
possibleconfigurationsoflabels(top:asimpleface;bottom:a
confluentface).

Classicalvariantsofthisdefinitionareobtainedbyreplacingquadrangulations
with
n
facesbytriangulationswith2
n
triangles,orby(vertex-)4-regularmaps
with
n
vertices,orbyallplanarmapswith
n
edges,
etc.
Alltheserandomplanar
latticeshavebeenconsideredbothincombinatorics(see[6]andreferencestherein)
andinmathematicalphysics(see[3]andreferencestherein;inthephysicsliterature,
definitionsareusuallyphrasedusing“symmetryweights”insteadofrootedobjects,
butthisisstrictlyequivalenttothecombinatorialdefinition).Althoughdetailsof
localtopologyvarybetweenfamilies,mostprobabilisticpropertiesarebelievedto
be“universal”,thatisqualitativelyanalogueforall“reasonable”families.Observe
alsothatrandommapsinclassicalfamilieshaveexponentiallysmallprobabilityto
besymmetric,sothatallresultsholdaswellinthemodelofuniformunrooted
maps[29].
Inthisarticlewefocusonquadrangulationsbecauseoftheircombinatorialrela-
tion,detailedinSection3,towelllabelledtrees.

2.3.
Theprofileofamap.
Thedistance
d
(
x,y
)betweentwovertices
x
and
y
of
amapistheminimalnumberofedgesonapathfrom
x
to
y
(inothertermsall
edgeshaveabstractlength1).
The
profile
ofarootedmap
M
isthesequence(
H
k
)
k

1
,where
H
k

H
k
[
M
]
isthe
numberofverticesatdistanc

e
k
oftherootvertex
v
0
.Weshallalsoconsiderthe
cumulatedprofile
H

k
[
M
]
=
k
=1
H

[
M
]
.Byconstructionthesupportoftheprofile
ofarootedmapisaninterval
i.e.
{
k
|
H
k
>
0
}
=[1
,r
]where
r
isthe
radius
of
themap(sometimesalsocalled
eccentricity
).Theradius
r
iscloselyrelatedtothe
diameter
,thatisthelargestdistancebetweentwoverticesofamap:inparticular
r

d

2
r
.ThequadrangulationofFigure3hasradius3.
)n(The
profileoftherandomplanarlattice
L
n
istherandomvariable(
H
k
)
k

1
that
isdefinedbytakingtheprofile(
H
k
[
L
n
]
)
k

1
ofaninstanceof
L
n
,while(
H

k
(
n
)
)
k

1
denotesthe
cumulated
profileof
L
n
.Similarlytheradiusofarandomplanarlattice
isapositiveintegervaluedrandomvariable
r
n
.

3.
Encodingtheprofilewithwelllabelledtrees

RANDOMMAPSANDISE

1

=4
112312

=4
2

=1
322ekaf13 =

7

Figure4.
Awelllabelledtreewithitslabeldistribution.
3.1.
Welllabelledtreesandtheencodingresult.
A
planetree
isarooted
planarmapwithoutcycle(andthuswithonlyoneface).Equivalentlyplanetrees
canberecursivelydefinedasfollows:

thesmallesttreeismadeofasinglevertex,

anyothertreeisanon-emptysequenceofsubtreesattachedtoaroot.
Inotherterm,eachvertexhasapossiblyemptysequenceofsons,andeachvertex
buttheroothasafather.Thenumberofplanetreeswith
n
edgesisthewellknown
Catalannumber

C
(2
n
)=12
n.
n1+nAplanetreeis
welllabelled
ifallitsverticeshavepositiveintegerlabels,the
labelsoftwoadjacentverticesdifferatmostbyone,andthelabeloftheroot
vertexisone.Let
W
n
denotethesetofwelllabelledtreeswith
n
edges.
]T[The
labeldistribution
ofawelllabelledtree
T
isthesequence(
λ
k
)
k

1

(
λ
k
)
k

1
]T[where
λ
k
isthenumberofverticeswithlabel
k
inthetree
T
.Thecumulatedlabel
distributionisdefinedby
λ

[
kT
]
=
k
=1
λ
[
T
]
.Byconstructionthesupportofthelabel
distributionisaninterval:thereexistsaninteger
µ
suchthat
{
k
|
λ
k
>
0
}
=[1

].
Thisinteger
µ
isthemaximallabelofthetree.Thesedefinitionsareillustratedby
Figure4.
Thefollowingtheoremwillserveustoreducethestudyoftheprofileofquad-
rangulationstothestudyofthelabeldistributionofwelllabelledtrees.
Theorem1
(Schaeffer[31])
.
Thereexistsabijection
T
betweenrootedquadran-
gulationswith
n
facesandwelllabelledtreeswith
n
edges,suchthattheprofile
(
H
k
[
Q
]
)
k

1
ofaquadrangulation
Q
ismappedontothelabeldistribution
(
λ
[
kT
]
)
k

1
ofthetree
T
=
T
(
Q
)
.
Theorem1andTutte’sformula(1)implythatthenumberofwelllabelledtrees
with
n
edgesequals
23
n

2
n

(2)
|W
n
|
=
n
+2
n
+1
n.
ThisresultwasprovedalreadybyCoriandVauquelin[13],whointroducedwell
labelledtreestogiveanencodingofallplanarmapswith
n
edges.Becauseof
aclassicalbijectionbetweenthelattermapsandquadrangulationswith
n
faces,
theirresultisequivalenttothefirstpartofTheorem1.Theirbijectionhasbeen
extendedtobipartitemapsbyArqu`es[5]andtohighergenusmapsbyMarcusand

8

CHASSAINGANDSCHAEFFER
ee+1e+1
1
13e+2
2122121321
e2e+1e+1
122
ekaf10e

Figure5.
TherulesofselectionofedgesandtheexampleofFigure3.
Vauquelin[25].Alltheseconstructionswererecursiveandbasedonencodingsof
mapswithpermutations(alsoknownasrotationsystems).
However,ourinterestinwelllabelledtreesliesintherelationbetweentheprofile
andthelabeldistribution,whichdoesnotappearinCoriandVauquelin’sbijection.
Thebijectionweusehereismuchsimplerandimmediatelyleadstothesecondpart
ofTheorem1.ThisapproachwasextendedtononseparablemapsbyJacquard
[20]andtohighergenusbyMarcusandSchaeffer[24].
WepostponetoSection4thediscussionoftheinterestingformofFormula(2)
anditsrelationtoCatalannumbers.Insteadtherestofthispartisconcerned
withtheproofofTheorem1,whichgoesinthreesteps.Firstsomepropertiesof
distancesinquadrangulationsareindicated(Section3.2).Thisallowsinasecond
steptodefinetheencoding,asamapping
T
fromquadrangulationstowelllabelled
trees(Section3.3).Adecodingprocedureallowsthentoprovethat
T
isfaithful
(Section3.4).
3.2.
Propertiesofdistancesinaquadrangulation.
Let
Q
bearootedquad-
rangulationanddenote
v
0
itsrootvertex.Thelabelling
φ
ofthemap
Q
isde-
finedby
φ
(
x
)=
d
(
x,v
0
)foreachvertex
x
,where
d
(
x,y
)denotesthedistancein
Q
(cf.Figure3).Observethatthenumberofverticeswithlabel
k
inthela-
be
[
l
Q
li
]
ngofthemap
Q
ispreciselythenumberofverticesatdistance
k
of
v
0
,thatis
H
k
=
|{
x
|
φ
(
x
)=
k
}|
.Thislabellingsatisfiesthefollowingimmediateproperties:
Property1.
If
x
and
y
arejoinedbyanedge,
|
φ
(
x
)

φ
(
y
)
|
=1
.Indeedthe
quadrangulationbeingbipartite,avertex
x
iswhiteifandonlyif
φ
(
x
)
iseven,
blackifandonlyif
φ
(
x
)
isodd.
Property2.
Aroundaface,fourverticesappear:ablack
x
1
,awhite
y
1
,ablack
x
2
andawhite
y
2
.Theseverticessatisfyatleastoneofthetwoequalities
φ
(
x
1
)=
φ
(
x
2
)
or
φ
(
y
1
)=
φ
(
y
2
)
(cf.Figure3).
Afacewillbesaid
simple
whenonlyoneequalityissatisfiedand
confluent
otherwise(seeFigure3).Itshouldbenotedthatonemayhave
x
1
=
x
2
or
y
1
=
y
2
.
3.3.
Constructionoftheencoding
T
.
Let
Q
bearootedquadrangulationwith
itsdistancelabelling.Themap
Q

isobtainedbydividingallconfluentfaces
Q
into
twotriangularfacesbyanedgejoiningthetwoverticeswithmaximallabel.Letus
nowdefineasubset
T
(
Q
)ofedgesof
Q

bytwoselectionrules:
Ineachconfluentfaceof
Q
,theedgethatwasaddedtoform
Q

isselected.


•RANDOMMAPSANDISE

e1e1
eeeee+1
e1e+1
e1e

9

Figure6.
Impossibilityofcycles.
Foreachsimpleface
f
of
Q
,let
v
bethevertexwithmaximallabelin
f
,then
theedgeleaving
v
with
f
onitsleftisselected.
Observethatsincemapsaredefinedonthesphere,theinfinitefaceinaplanarrep-
resentationcontributesaswelltoanedge.Thesetwoselectionrulesareillustrated
byFigure5.Therootof
T
(
Q
)isdefinedtobethefirstedgeof
T
(
Q
)aroundthe
endpointoftherootof
Q
,counterclockwise,startingfromtherootof
Q
.
TheproofofTheorem1isnowcompletedintwosteps.First,intherestofthis
section,
T
(
Q
),whichis
apriori
onlydefinedasasubsetofedgesof
Q

together
withtheirincidentvertices,isshowntobeinfactawelllabelledtreewith
n
edges.
Second,inthenextsectiontheinversemappingisdescribedandusedtoprovethat
themapping
T
isfaithful.
Proposition1.
Themapping
T
sendsaquadrangulation
Q
with
n
facesonawell
labelledtreewith
n
edges.
Proof.
Ifthevertex
x
isnottherootof
Q
,thenoneofitsneighborsin
Q
,say
y
,
hasasmallerlabel.Theedge(
x,y
)canbeincidentto:atleastaconfluentface;at
leastasimplefaceinwhich
x
hasmaximallabel;ortwosimplefacesinwhich
x
has
intermediatelabel.Inallthreecases,
x
isincidenttotheselectededgeofatleast
oneface.Thusallverticesof
Q
butitsrootarealsoverticesof
T
(
Q
):inparticular
T
(
Q
)has
n
+1vertices.Next,thenumberofedgesof
T
(
Q
)is
n
,becausethisis
thenumberoffacesof
Q
andtwofacescannotselectthesameedge(asimmediately
followsfrominspectionoftheselectionrules).Nowtheplanarityof
Q
andthusof
Q

grantsthateachconnectedcomponentof
T
(
Q
)isplanar.Providedwecanrule
outcycles,thisimplythat
T
(
Q
)isaforestoftreeswith
n
edgesand
n
+1vertices,
i.e.
asingletree.Thistreeisthenclearlywelllabelled.
Supposenowthatthereexistsacyclein
T
(
Q
)andlet
e

0bethevalueofthe
smallestlabelofavertexofthiscycle.Eitheralltheselabelsareequalto
e
,orthere
isinthecycleanedge(
e,e
+1)andanedge(
e
+1
,e
).Inbothcasestherulesof
selectionofedgesimplythateachconnectedcomponentof
Q

definedbythecycle
containsavertex
x
(resp.
y
)withlabel
e

1,asshownbyFigure6.Accordingto
Jordan’stheorem,eithertheshortestpathfrom
x
totherootortheshortestpath
from
y
totheroothastointersectthecycle,leadingtoacontradictionwiththe
definitionoflabelsbydistances.Therearethusnocyclesand
T
(
Q
)isatree.
3.4.
Theinverse
Q
ofthemapping
T
.
Let
T
beawelllabelledtreewith
n
edges.Recallthatthetree
T
canbeviewedasaplanarmapthathasaunique

01

CHASSAINGANDSCHAEFFER

32221121
543
2212111060Figure7.
Step(1),andthechords(
i,s
(
i
))inoneofthefaces.

face
F
0
.A
corner
isasectorbetweentwoconsecutiveedgesaroundavertex.A
vertexofdegree
k
defines
k
corners(inparticularaleafdefinesonecorner).The
totalnumberofcornersof
T
is2
n
.Thelabelofacornerisbydefinitionthelabel
ofthecorrespondingvertex.
Theimage
Q
(
T
)isdefinedinthreesteps.
1.Avertex
v
0
withlabel0isplacedintheface
F
0
andoneedgeisaddedbetween
thisvertexandeachofthe

cornerswithlabel1.Thenewrootistakento
betheedgearrivingfrom
v
0
atthecornerbeforetherootof
T
.
AfterStep(1)auniquelydefinedrootedmap
T
0
with

faceshasbeenobtained
(seeFigure7,with

=5).Thenextstepstakeplaceindependentlyineachofthose
facesandarethusdescribedforageneric
2
face
F
of
T
0
.Let
k
bethedegreeof
F
(byconstruction
k

3).Amongthecornersof
F
,onlyoneisincidentto
v
0
and
haslabel0.Letthecornersbenumberedfrom1to
k
inclockwiseorderalongthe
border,startingrightafter
v
0
.Letmoreover
e
i
bethelabelofcorner
i
(sothat
e
1
=
e
k

1
=1and
e
k
=0).InFigure7,thecornersofafacearerepresentedwith
theirnumberingandlabels.
2.Thefunctionsuccessor
s
isdefinedforallcorners1
,...,k

1by
s
(
i
)=inf
{
j>i
|
e
j
=
e
i

1
}
.
Foreachcorner
i

2suchthat
s
(
i
)

=
i
+1,achord(
i,s
(
i
))isaddedinside
theface,insuchawaythatthevariouschordsdonotintersect(Property3).
Oncethisconstructionhasbeencarriedonineachface,aplanarmap
T

isobtained.
3.Alledgesofwithlabelsoftheform(
e,e
)of
T

aredeleted.Theresultingmap
isaquadrangulation
Q
(
T
)with
n
faces(Property4).
ThefollowingpropositionendstheproofofTheorem1.
Proposition2.
Themapping
Q
istheinversebijectionofthemapping
T
.
Letusfirstprovethetwopropertiesthatvalidatetheprecedingconstruction.
Property3.
Thechords
(
i,s
(
i
))
donotintersect.
Proof.
Supposethattwochords(
i,s
(
i
))and(
j,s
(
j
))crosseachother.Uponmaybe
exchanging
i
and
j
onehas
i<j<s
(
i
)
<s
(
j
).Thefirsttwoinequalitiesimply,
togetherwiththedefinitionof
s
,that
e
j
>e
s
(
i
)
,whilethetwolastinequalities
imply
e
s
(
i
)

e
j
.Thisisacontradiction.
2
Theinfinitefaceisonlyapparentlydifferentfromtheothers:imaginethemaponthesphere.