NON-RECURSIVE COUNTS OF GRAPHS ON SURFACES NICHOLAS ERCOLANI1 JOCELINE LEGA2 AND BRANDON TIPPINGS3 Abstract. The problem of map enumeration concerns counting connected spatial graphs with a

2025-05-02 0 0 841.64KB 29 页 10玖币

侵权投诉

NON-RECURSIVE COUNTS OF GRAPHS ON SURFACES

NICHOLAS ERCOLANI1, JOCELINE LEGA2, AND BRANDON TIPPINGS3

Abstract. The problem of map enumeration concerns counting connected spatial graphs, with a

speciﬁed number jof vertices, that can be embedded in a compact surface of genus gin such a way

that its complement yields a cellular decomposition of the surface. As such this problem lies at the

cross-roads of combinatorial studies in low dimensional topology and graph theory. The determi-

nation of explicit formulae for map counts, in terms of closed classical combinatorial functions of g

and jas opposed to a recursive prescription, has been a long-standing problem with explicit results

known only for very low values of g. In this paper we derive closed-form expressions for counts of

maps with an arbitrary number of even-valent vertices, embedded in surfaces of arbitrary genus. In

particular, we exhibit a number of higher genus examples for 4-valent maps that have not appeared

prior in the literature.

Keywords: map enumeration, analytical combinatorics, hypergeometric functions, transfer matri-

ces

Mathematics Subject Classiﬁcations: 05A15, 05A10, 33C05, 33C20, 39A60, 57K20

1. Introduction

This article concerns map enumeration, a topic that brings together the classical subjects of

graphical enumeration and low-dimensional combinatorial topology. This subject has a long history

going back to the work of Tutte and his school in the 60’s. We refer to [Tu68] for a contemporaneous

survey of that early work. Tutte’s original interest concerned rooted planar maps, which correspond

to unlabeled connected graphs embedded in the sphere (or equivalently the plane) that are rooted.

In this context, rooted means that a vertex of the graph, together with an edge adjacent to it and

a side of that edge, are distinguished. The deﬁnition of maps for higher genus is more involved (see

following paragraph) and enumerations in these cases are much more challenging to achieve. Some

early results for low genus surfaces using an extension of the idea of rooted maps were carried out by

Brown [Br66] and Arques [Ar87]. Tutte’s recursive approach was extended by Bender and Canfeld

[BC86], who initiated the study of asymptotic (in vertex number) enumerations for general surfaces.

A reﬁned version of their recursion was subsequently obtained by Eynard [Ey16]. Over the years,

a number of related but alternative approaches to the enumeration problem have been developed.

These too are recursive and combinatorial in nature, as described in [CMS09], [BG12] and the

references therein. The present study establishes non-recursive map counts, through an approach

grounded in analytical statistical physics, as described in the remainder of this introduction. Our

results have a number of interesting current and potential applications in their own right. In

particular, the asymptotic enumerations derived in [BC86] can be directly obtained from the exact

closed form expressions (2.4) and (2.6) used in this paper (see section 4.2).

We deﬁne a map to be a connected, labeled graph embedded injectively into a compact, oriented

and connected topological surface so that the complement of the graph in the surface is a disjoint

union of cells (sets homeomorphic to open discs). Labeling means that vertices as well as the

half-edges (referred to as darts) are labeled counter-clockwise around each vertex. This sets up a

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.00671v3 [math.CO] 8 May 2023

NON-RECURSIVE COUNTS OF GRAPHS ON SURFACES 2

Figure 1. Top: 4-valent map with 5 vertices on a torus. The numbers are dart

labels and the colors represent the quadrilateral tiling induced by the dual graph.

Bottom: Illustration of the resulting tiling of the torus with quadrilaterals.

correspondence between matchings, pairwise, of dart arrangements and equivalence classes of maps.

Due to surface symmetries, this correspondence is not quite 1:1. Indeed, two labeled maps are said

to be equivalent if there is an orientation-preserving homeomorphism of the surface to itself that

leaves the graph unchanged. For ﬁxed graph size (i.e. for a ﬁxed number of vertices), the number

of non-equivalent dart matchings (for a surface of ﬁxed genus) is ﬁnite. This number is what we

refer to as a map count. Quotienting these counts by the cardinality of all possible labelings, which

for a map of size jis j! (2ν)j, would then seem to yield a more geometric count of maps under a

coarser equivalence relation that does not involve labelings. However due to the possibility of a

surface having symmetries, our map counts will not in general be divisible by the afore-mentioned

labeling cardinality. This is in complete analogy with descriptions of moduli spaces of conformal

structures on Riemann surfaces [Na91], where symmetries lead to orbifold singularities on those

spaces. We refer to [EM03,EW22] and references therein for further details. The top panel of

Figure 1provides an example of the correspondence between dart matchings and maps. This ﬁgure

also illustrates the connection between surface topology and graph theory that map enumeration

provides: one sees that the dual map associated to the graph, viewed as a 4-valent dart matching,

yields a surface tessellation, or tiling, by topological quadrilaterals.

In this paper we will restrict attention to two related cases: (a) maps whose vertices are all of

degree 2ν(the regular 2ν-valent case) whose count will be denoted by N2ν,e(g, j), and (b) maps with

jvertices of degree 2ν, and two additional vertices of degree 1, with count denoted by N2ν,z(g, j).

By deﬁnition the additional two vertices in the latter case each have a unique adjacent edge referred

to as a leg. For case (b) the symmetries alluded to earlier are absent [ELT22b] and so the map

NON-RECURSIVE COUNTS OF GRAPHS ON SURFACES 3

counts are each divisible by j! (2ν)j. Hence, in this case the quotient counts the number of coarser

map equivalence classes without labeling.

As previously mentioned, the method we employ to calculate map counts stems from statistical

physics and more precisely from application of the Wick calculus to perturbation expansions of the

random matrix partition function (for hermitian ensembles) and its correlation functions (referred

to as genus expansions). This gives rise to a hierarchy of equations that recover generating functions

for the map counts as coeﬃcients in the genus expansions [EM03]. These functions have the general

form ∞

j=0

N(g, j)

j!tj.

In what follows we denote the generating functions for counts of maps of genus g(g-maps) in case

(a) by eg, and in case (b) by zg. The two are intimately related. In particular, the egmay be

determined from the zgby solving a forced Cauchy-Euler equation [EMP08].

There are two approaches in the literature for deriving recursion equations for the map gener-

ating functions from the genus expansions. One of these is based on the matrix resolvent (Green’s

function) for random matrices [ACKM93,Ey16]. This is often referred to as the topological recur-

sion. The other is based on the recurrence matrix resolvent of orthogonal polynomials associated

to the probability measure of the random matrix ensemble [EM03,EMP08,BD13,EW22]. In the

latter approach one is able to bring to bear rigorous analytical methods from the classical theory

of orthogonal polynomials as well as Riemann-Hilbert analysis in order to get detailed estimates

on the validity of the genus expansion and associated recurrence equations. This enables one to

establish that the generating functions of the form displayed above, initially taken to be formal,

are in fact convergent [EM03] and to determine their maximal domains of holomorphy. This is

essential for the derivation of explicit closed rational expressions for the zginitiated in [Er11] and

continued in [ELT22b] that we use. We refer the reader to the last citation for additional details

and will take as our starting point the rational expressions for zgand egthat were developed in

[EMP08,Er11,Er14].

While map enumeration has stemmed from recursion schemes of the type just mentioned, what

we do in this paper is decidedly diﬀerent. We aim to derive expressions for the map counts N(g, j)

that are of closed form in terms of known classical combinatorial functions. This is what we refer to

as a non-recursive count. A few examples are available in the literature: N2ν,z(0, j) and N2ν,e(0, j)

were derived in [EMP08], N4,e(2, j) was introduced in [BIZ80], and more recently, N4,e(3, j) was

obtained in [BGM21]. To the best of our knowledge, the only other instances of known closed-form

expressions are N3,e(0, j) and N3,e(1, j), for triangulations on a surface of genus 0 or 1 [BD13].

This article establishes general expressions for N2ν,z(g, j) and N2ν,e(g, j) in terms of a linear com-

bination of a speciﬁed set of coeﬃcients appearing in the rational forms for zgand eg, weighted

by hypergeometric functions depending on the genus gand the number of vertices j. In addition,

we introduce a dynamic perspective which, in the case of 4-valent maps, leads to a remarkable

analytical simpliﬁcation that enables us to eﬃciently express the desired non-recursive counts in

terms of polynomials, powers, and factorials of the number of vertices j, for ﬁxed but arbitrary

genus, as shown in Tables 1and 2below. These tables suggest a general structure for the counts

N4,z(g, j) and N4,e(g, j) of the form

N4,z(g, j) = (−1)g12j 2g−2

k=0

(j−k)!(2j)!

j!P(g)

bg/2c(j)−4jj!P(g)

b(g−1)/2c(j), g ≥1, j ≥0

and

N4,e(g, j) = (−1)g12j−1 2g−3

k=1

(j−k)!(2j)!

j!Q(g)

bg/2c(j)−4j−1j!Q(g)

b(g−1)/2c(j), g ≥2, j ≥1

NON-RECURSIVE COUNTS OF GRAPHS ON SURFACES 4

where P(g)

h(j) and Q(g)

h(j) denote polynomials of degree hin jwhose coeﬃcients are positive rational

numbers that depend only on g. The reduction leading to these expressions works for all genera in

the case of N4,z(g, j), and for g≥2 in the case of N4,e(g, j). Counts of regular genus 1 maps are

indeed special, and we provide a separate derivation for N4,e(1, j) in Appendix A.

genus gN4,z(g, j)

1 12jj4jj!

12 −(2j)!

6j!

2 12j 2

k=0

(j−k)!(2j)!

7(2j+ 3)

1080 −4jj!7

384

3 12j 4

k=0

(j−k)!4jj!245j

497664 +12041

4976640−(2j)!

484j+ 279

136080 

12j 6

k=0

(j−k)!(2j)!

j!37079

750578400j2+6067121

10508097600j+127

604800

−4jj!7805j

47775744 +1699447

6688604160

12j 8

k=0

(j−k)!4jj!38213

27518828544j2+1702225

55037657088j+482999

20384317440

−(2j)!

j!491951

25519665600j2+1849339

25519665600j+73

3421440

12j 10

k=0

(j−k)!(2j)!

j!5004682489

45165980162160000j3+389578665043

92213876164410000j2

+69512878587263

8852532111783360000j+1414477

653837184000

−4jj!54362497

87179648827392j2+381046393

87179648827392j

+43567716553

20341918059724800

12j 12

k=0

(j−k)!4jj!6334396069

2448004539073167360j3+2801562779

18133366956097536j2

+5032281513503

9792018156292669440j+46115735865131

228480423646828953600

−(2j)!

j!953637649

16937242560810000j3+335779266491

491807339543520000j2

+20962080883129

26557596335350080000j+8191

37362124800

Table 1. Expressions for the number of 2-legged 4-valent g-maps with jvertices.

NON-RECURSIVE COUNTS OF GRAPHS ON SURFACES 5

genus gN4,e(g, j)

1j! 12j−12j−1

j−13F21,1,1−j

2, j + 1 ;−1−2j−1

j−23F21,1,2−j

2, j + 2 ;−1

2(∗)12j−1(j−1) (2j)!

j!7j

90 +1

40−4j−1j!13

48

3(∗)12j−1 3

k=1

(j−k)!4j−1j!245j

20736 +781

41472−(2j)!

j!337j

22680 +1

1008

12j−1 5

k=1

(j−k)!(2j)!

j!37079

125096400j2+86356

54729675j+1

28800

−4j−1j!5845j

1990656 +23297

39813120

12j−1 7

k=1

(j−k)!4j−1j!38213

1146617856j2+915313

2293235712j−1940327

53508833280

−(2j)!

j!211033

2319969600j2+8139013

71455063680j+1

887040

12j−1 9

k=1

(j−k)!(2j)!

j!5004682489

7527663360360000j3+7523688218141

491807339543520000j2

+20903746897

3944978659440000j+691

19813248000

−4j−1j!44274265

3632485367808j2+135152437

3632485367808j

−522404797

77052719923200

12j−1 11

k=1

(j−k)!4j−1j!6334396069

102000189128048640j3+27364604401

11333354347560960j2

+988175350991

408000756512194560j−358193577649

732309050150092800

−(2j)!

j!25511722279

90331960324320000j3+2675917530049

1475422018630560000j2

+5035943441

69980491002240000j+1

958003200

Table 2. Expressions for the number of 4-valent g-maps with jvertices (j≥1).

In the ﬁrst row, 3F2is the generalized hypergeometric function. Starred (∗)rows

correspond to results previously known in the literature: [BIZ80] for g= 2 and

[BGM21] for g= 3.

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

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

10 玖币 0人已下载

立即下载

摘要：

NON-RECURSIVECOUNTSOFGRAPHSONSURFACESNICHOLASERCOLANI1,JOCELINELEGA2,ANDBRANDONTIPPINGS3Abstract.Theproblemofmapenumerationconcernscountingconnectedspatialgraphs,withaspeciednumberjofvertices,thatcanbeembeddedinacompactsurfaceofgenusginsuchawaythatitscomplementyieldsacellulardecompositionofthesurfa...

展开>> 收起<<

NON-RECURSIVE COUNTS OF GRAPHS ON SURFACES NICHOLAS ERCOLANI1 JOCELINE LEGA2 AND BRANDON TIPPINGS3 Abstract. The problem of map enumeration concerns counting connected spatial graphs with a.pdf

共29页,预览5页

还剩页未读，继续阅读

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

NON-RECURSIVE COUNTS OF GRAPHS ON SURFACES NICHOLAS ERCOLANI1 JOCELINE LEGA2 AND BRANDON TIPPINGS3 Abstract. The problem of map enumeration concerns counting connected spatial graphs with a

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: