MULTIPLE SCALE ASYMPTOTICS OF MAP ENUMERATION NICHOLAS ERCOLANI1 JOCELINE LEGA2 AND BRANDON TIPPINGS3 Abstract. We introduce a systematic approach to express generating functions for the enumeration of maps

2025-05-02 0 0 1.19MB 30 页 10玖币

侵权投诉

MULTIPLE SCALE ASYMPTOTICS OF MAP ENUMERATION

NICHOLAS ERCOLANI1, JOCELINE LEGA2, AND BRANDON TIPPINGS3

Abstract. We introduce a systematic approach to express generating functions for the enumeration of maps

on surfaces of high genus in terms of a single generating function relevant to planar surfaces. Central to

this work is the comparison of two asymptotic expansions obtained from two diﬀerent ﬁelds of mathematics:

the Riemann-Hilbert analysis of orthogonal polynomials and the theory of discrete dynamical systems. By

equating the coeﬃcients of these expansions in a common region of uniform validity in their parameters,

we recover known results and provide new expressions for generating functions associated with graphical

enumeration on surfaces of genera 0 through 7. Although the body of the article focuses on 4-valent maps,

the methodology presented here extends to regular maps of arbitrary even valence and to some cases of odd

valence, as detailed in the appendices.

1. Introduction

This paper combines ideas from random matrix theory and dynamical systems to address a long-standing

question relevant to a particular branch of graph theory, speciﬁcally the enumeration of maps. This branch

of graphical enumeration arose in the mid-twentieth century as a ﬁrst step in addressing the following general

question: given a spatial graph, when can that graph be embedded on a particular type of topological surface?

Some graphs are planar, meaning the graph can be embedded in a plane (or equivalently a sphere) without

being forced to cross itself. The same question can be posed for more general surfaces, thereby setting up a

kind of complexity classiﬁcation of spatial graphs, or networks, in terms of the topology of surfaces on which

they can or cannot be embedded.

Being able to enumerate graphs subject to topological complexity serves as a ﬁrst step in understanding

the general role of topological frustration in network theory. There have been quite a few studies in the

physics and mathematics literature related to this problem and in particular toward the construction of

generating functions for this enumeration indexed by graph size (the number of vertices, which we will

denote j). Because the graph size is not bounded, this potentially involves an inﬁnite amount of information

for each topological surface. However, it was shown in [Er11] that these generating functions depend only on

a minimal, speciﬁc, ﬁnite set of rational parameters. The results discussed in this paper develop a systematic

method for identifying these parameters explicitly.

Amap is a connected graph Γ embedded in a surface Mthat satisﬁes certain additional conditions. The

surfaces we consider are compact, oriented and connected topological surfaces, each of them being uniquely

speciﬁed, up to a homeomorphism, by its genus, g. Embedding a graph, Γ, into Mamounts to embedding

its vertices and edges in such a way that the overall placement of the graph on Mis injective and continuous.

The last additional condition required is that after the surface is cut along the edges of the embedded graph,

what remains is a disjoint union of contractible topological cells. For ﬁxed genus g, we refer to maps satisfying

these conditions as g-maps.

A depiction of a map in a local chart on a surface is illustrated by the dashed black graph embedded in

a planar region shown in Figure 1. Note that in this example all (black) vertices have valence 4 (in the

graph-theoretic sense). Maps whose vertices all have the same valence, V, are referred to as V-regular maps

in analogy with the terminology for graphs. Figure 1also (locally) illustrates the dual map (depicted in

terms of the solid blue graph). The 4-regularity of the original map results in the dual map being a tiling of

the surface by topological rectangles.

1University of Arizona, Department of Mathematics (ercolani@math.arizona.edu).

2University of Arizona, Department of Mathematics (lega@math.arizona.edu, www.math.arizona.edu/~lega/),

3University of Arizona, Department of Mathematics (tippings@arizona.edu).

arXiv:2210.00668v2 [math-ph] 30 Dec 2022

MULTIPLE SCALE ASYMPTOTICS OF MAP ENUMERATION 2

Figure 1. Illustration of a 4-valent map in a local chart and of its dual.

Such surface tilings arise in a number of settings where one may be interested in modelling some kind

of large scale cellular growth subject to global topological constraints. Physical applications arise in pat-

tern formation in foams [Ba99], planar systems of interacting particles [Le11], embryo gastrulation [MB14],

and vertex dynamics [FOMG13]. For related statistical or stochastic questions (such as statistical mechan-

ics/dynamics on random networks [HS21] or stochastic Loewner evolution of interfaces [CN06]) the large

scale enumeration of maps with ﬁxed features is an important initial problem.

As mentioned earlier, we are interested in the enumeration of maps with a ﬁxed number, j, of vertices as

jvaries and becomes large. To reduce such enumerations to a combinatorial question, one needs to deﬁne

when two maps are equivalent. One counts maps modulo equivalence and the set of equivalence classes is

ﬁnite. On a genus gsurface, two maps are equivalent if there is an orientation-preserving homeomorphism

from the surface to itself that induces a homeomorphism of the graph to itself preserving the sets of vertices

and edges but possibly respectively permuting them (while still preserving the incidence relations) [LZ04].

Equivalences for which such a permutation is non-trivial can arise. To avoid such technicalities at the

outset, it is typical to consider the enumeration of labelled maps. These are maps in which the vertices are

labelled (or numbered) and the edges around each vertex on the surface are also labelled consistent with the

orientation of the surface. For the latter it suﬃces to label one initial edge. The orientation (say clockwise)

will then order the successive numbering of the remaining edges around that vertex. This labelling breaks

any symmetries that could yield a non-trivial automorphism of Γ.

The earliest work on map enumeration goes back to Tutte [Tu68], using a purely combinatorial approach.

Further results in this vein have continued up to the present time, producing some remarkable combinatorial

insights [LZ04,JV90,BGR08,CMS09,Ch09]. Separately, deep and surprising connections to random matrix

theory have led to generating functions for map enumeration. These generating functions are series, one for

each genus g, whose jth Taylor coeﬃcient counts the number of labelled maps on the surface with jvertices of

prescribed valence. One of the earliest approaches was based on a formal application of resolvent identities

for random matrices that goes back to Ambjorn, Chekov, Kristjansen, and Makeenko [ACKM93]. This

is known as the method of loop equations. Eynard [Ey11,Ey16] subsequently improved on this work to

establish a direct connection between loop equations and Tutte’s equations that are key to the combinatorial

method mentioned earlier. Finally, in [BIZ80] and, later in [FIK92], a diﬀerent random matrix approach

to deriving generating functions was developed based on recurrence relations for orthogonal polynomials.

Subsequently, a rigorous basis for deriving map generating functions in general was established in [EM03,

EMP08,BD16,EP12,EW22], and led to further insights into their structure. The present work builds on

these and recent results of the authors to compare two expansions, both centered on recurrence coeﬃcients

for orthogonal polynomials. One of the expansions considers these coeﬃcients in terms of their combinatorial

interpretation related to graphical enumeration discussed above. The other understands these coeﬃcients in

terms of an orbit embedded in a dynamical system known as the discrete Painlev´e I equation. Comparing

these two expansions in a region where they are both valid, as illustrated in Figure 2, provides a procedure

MULTIPLE SCALE ASYMPTOTICS OF MAP ENUMERATION 3

to systematically count the number of regular g-maps with ﬁxed number of vertices, for arbitrary values of

g. This procedure builds on an approach ﬁrst developed in [Tip20] (Section 7.4).

The rest of this article is organized as follows. Section 2introduces the two expansions, which we call

the genus expansion and the center manifold expansion. Section 3recasts them using the same gauge as the

asymptotic parameter n→ ∞, and identiﬁes a common region of validity where they can be equated term

by term. Section 4uses the result of Section 3to ﬁnd closed-form expressions for the generating functions of

labeled g-maps with 4-valent vertices, and illustrates the methodology in calculating the number of g-maps

with up to 15 vertices, for genera gbetween 0 and 7. Section 5summarizes our results and considers a

range of extensions. These include a generalization to 2ν-valent 2-legged maps that makes use of asymptotic

expansions available in the literature in lieu of the center manifold expansion, possible extensions of the

method of [ELT22] to higher-order Painlev´e equations, a discussion of triangulations, and the existence of

closed-form expressions for the number of 4-valent g-maps with an arbitrary number of vertices. For clarity,

the body of the article only considers 4-valent maps. Proofs of all of the theorems are presented in the

appendices, in the more general case of 2ν-valent maps.

Figure 2. The two expansions for ν= 2. Left: the genus expansion is valid as n→ ∞

for arbitrary values of r > 0 and α=n/N '1. Middle: the center manifold expansion is

valid as n→ ∞ for arbitrary positive values of rand N, here chosen such that r=n/ξ

and N=n/α. As n→ ∞, both rand Nincrease linearly with n, as suggested by the red

arrow. Right: in (ξ, α, n) coordinates, the regions of validity of the expansions overlap for

ﬁxed values of α'1 and ξ > 0.

2. The Two Expansions

2.1. Recurrence Relations and The Genus Expansion. We consider orthogonal polynomials deﬁned

on the real line with respect to an exponential weight of the form w(λ) = e−Vt,N (λ), where the potential Vt,N

is given by

Vt,N (λ) = N



2λ2+

j=1

tjλj

,t= (t1,··· , tJ) (2.1)

MULTIPLE SCALE ASYMPTOTICS OF MAP ENUMERATION 4

with Jeven. Although this paper will focus on a very particular case of (2.1), the general expression of Vt,N

given above will be relevant in some of the appendices. Given the weight w, one can deﬁne a family of monic

orthogonal polynomials {π`}that satisfy the conditions

πn(λ)πm(λ)w(λ)dλ = 0, n 6=m.

When the potential Vt,N (λ) in (2.1) is even, these polynomials are determined by a recurrence of the form

λ πn(λ) = πn+1(λ) + b2

nπn−1(λ).(2.2)

The results directly pertinent to map enumeration rest on a detailed analysis of the truncated Mercer kernel

associated to the family of monic orthogonal polynomials {π`},

Kt,n(λ, η) = e−(1/2)(Vt,N (λ)+Vt,N (η))

n−1

`=0

π`(λ)π`(η),

and its large nasymptotics. The fundamental result is the following so-called genus expansion.

Theorem 2.1. [EM03]There exist T > 0and γ > 0such that one has an asymptotic expansion, uniformly

valid for α=n

Nsuﬃciently close to 1 and all t∈T(T, γ) = nt∈RJ:|t| ≤ T, tJ> γ PJ−1

j=1 |tj|o, of the

form

Z∞

−∞

F(λ)Kt,n(λ, λ)dλ =F0(α, t) + n−2F1(α, t) + n−4F2(α, t) + ··· ,

provided the function F(λ)is C∞and grows no faster than polynomially. The coeﬃcients Fmdepend

analytically on αand tfor t∈T(T, γ)and the asymptotic expansion may be diﬀerentiated term by term

with respect to αand t.

This is referred to as a genus expansion because for various choices of F(λ) the coeﬃcient of n−2gis the

generating function for some map enumeration problem on a surface of genus g.

Remark 2.2. The discrete variable nin this theorem, and the discussion preceding it, appears in other

related contexts. In the setting of random matrix theory, brieﬂy mentioned in Section 1,nis the matrix

size, and a probability density on n×nHermitian matrices, M, is given by exp (−Tr Vt,N (M)) dM . In the

dynamical setting of the discrete Painlev´e I equation, to be discussed in Section 2.2,nlabels the discrete time

step. The parameters in tof course determine the precise polynomial potential but, more importantly, they

serve to identify diﬀerent universality classes for statistical or dynamical behaviors of the physical system

being modelled. Finally, the (continuous) parameter Nacts as a kind of inverse temperature in the random

matrix setting and α=n/N is used to describe natural scaling invariances in all the systems just mentioned,

as well as in this paper. In random matrix theory, αis called the ’tHooft parameter and is usually denoted

by x. Here we use αto avoid confusion with the dynamic variable xnwhich will be introduced later.

The particular form of the potential we will focus on for this paper is

V(λ) = N1

2λ2+r

4λ4,(2.3)

corresponding to t= (0,0,0, t)∈R4,t4=t=r/4. Although focusing on this quartic case may seem

restrictive from the viewpoint of general map enumeration, this was the case of original interest in the

physics literature [BIZ80]. For Vgiven by Equation (2.3), we have the following result, obtained by setting

F(λ) = λin Theorem 2.1, diﬀerentiating the resulting expansion term by term with respect to t1and then

setting t1= 0.

Theorem 2.3. [EMP08]For the recurrence coeﬃcients b2

nof the three-term recurrence (2.2), associated to

the weight with potential (2.3), let α=n/N be in a neighborhood of 1, and let thave positive real part. Then

as n→ ∞,b2

nhas an asymptotic expansion of the form

n=αz0(t, α) + 1

n2z1(t, α)···,(2.4)

MULTIPLE SCALE ASYMPTOTICS OF MAP ENUMERATION 5

uniformly valid on compact sets in t. The coeﬃcients are analytic functions in a neighborhood of 0 with

Taylor-Maclaurin expansion

zg(t, α) =

∞

j=0

(−1)jκ(g)

j!(αt)j

where κ(g)

jis the the number of labeled g-maps with j4-valent vertices and exactly two vertices that are

1-valent.

A 1-valent vertex together with its unique edge is called a leg. An example of a 4-valent, 2-legged, g-map is

shown in Figure 3.

Remark 2.4. By this result, one may regard zg(t, 1) as an exponential generating function for counting

inequivalent classes of 2-legged, 4-valent labelled g-maps. Making our earlier variable replacement one has

zg(t, 1) = zgr

4,1=

∞

j=0

(−1)jκ(g)

j! 4jrj.

Alternatively, one may consider P∞

j=1(−1)jˆκ(g)

jrj, where ˆκ(g)

j=κ(g)

j! 4j, as an ordinary generating function

for unlabelled 2-legged, 4-valent g-maps. Indeed, j!is the size of the permutation group acting on vertex

labels and 4jis the size of the product of the cyclic groups acting on the distinguished edge labelling at each

vertex. Then j! 4jis the cardinality of the orbit under the action of relabelling. This can be related to the

action of the cartographic group which acts as a subgroup of the group of permutations of all the half-edges,

called darts, attached to vertices. We refer the reader to [LZ04],[EMP08](Section 5.10), and [Pi06]for

more details on these matters, but the important upshot of these considerations is that due to the presence of

legs in the maps being enumerated, there are no non-trivial equivalences of the type mentioned in section 1.

Consequently, ˆκ(g)

jwill always be an integer. In what follows we will be using z0(r

4, α)where z0is uniquely

determined by (2.4). We note, however, that the coeﬃcients in the Taylor-Maclaurin expansion of zg(r

4, α)

alternate in sign and so must be respectively multiplied by (−1)jto recover ˆκ(g)

Figure 3. Illustration of a 2-legged 4-valent map on the plane (0-map).

We will also make use of the following results, corresponding to Theorem B3 of [Er11].

Proposition 2.5. [Er11]The asymptotic expansion (2.4) is uniformly valid in a strip of constant width

around the positive real t-axis. In addition, the coeﬃcients zg(r

4, α)have a maximal analytic continuation to

the full complex rplane minus the ray (−∞,−1

12α].

We remark that this stated uniformity also follows independently from a result due to Bleher and Its [BI05].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

MULTIPLESCALEASYMPTOTICSOFMAPENUMERATIONNICHOLASERCOLANI1,JOCELINELEGA2,ANDBRANDONTIPPINGS3Abstract.Weintroduceasystematicapproachtoexpressgeneratingfunctionsfortheenumerationofmapsonsurfacesofhighgenusintermsofasinglegeneratingfunctionrelevanttoplanarsurfaces.Centraltothisworkisthecomparisonoftwoas...

展开>> 收起<<

MULTIPLE SCALE ASYMPTOTICS OF MAP ENUMERATION NICHOLAS ERCOLANI1 JOCELINE LEGA2 AND BRANDON TIPPINGS3 Abstract. We introduce a systematic approach to express generating functions for the enumeration of maps.pdf

共30页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

MULTIPLE SCALE ASYMPTOTICS OF MAP ENUMERATION NICHOLAS ERCOLANI1 JOCELINE LEGA2 AND BRANDON TIPPINGS3 Abstract. We introduce a systematic approach to express generating functions for the enumeration of maps

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: