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
specified 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 Classifications: 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 definition 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 refined 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 define 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).
1
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 fixed graph size (i.e. for a fixed number of vertices), the number
of non-equivalent dart matchings (for a surface of fixed genus) is finite. 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 figure
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 definition 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 coefficients in the genus expansions [EM03]. These functions have the general
form ∞
X
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 different. 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 specified set of coefficients 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 simplification that enables us to efficiently express the desired non-recursive counts in
terms of polynomials, powers, and factorials of the number of vertices j, for fixed 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
Y
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
Y
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 coefficients 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 12jj4jj!
12 −(2j)!
6j!
2 12j 2
Y
k=0
(j−k)!(2j)!
j!
7(2j+ 3)
1080 −4jj!7
384
3 12j 4
Y
k=0
(j−k)!4jj!245j
497664 +12041
4976640−(2j)!
j!
484j+ 279
136080
4
12j 6
Y
k=0
(j−k)!(2j)!
j!37079
750578400j2+6067121
10508097600j+127
604800
−4jj!7805j
47775744 +1699447
6688604160
5
12j 8
Y
k=0
(j−k)!4jj!38213
27518828544j2+1702225
55037657088j+482999
20384317440
−(2j)!
j!491951
25519665600j2+1849339
25519665600j+73
3421440
6
12j 10
Y
k=0
(j−k)!(2j)!
j!5004682489
45165980162160000j3+389578665043
92213876164410000j2
+69512878587263
8852532111783360000j+1414477
653837184000
−4jj!54362497
87179648827392j2+381046393
87179648827392j
+43567716553
20341918059724800
7
12j 12
Y
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−13F21,1,1−j
2, j + 1 ;−1−2j−1
j−23F21,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
Y
k=1
(j−k)!4j−1j!245j
20736 +781
41472−(2j)!
j!337j
22680 +1
1008
4
12j−1 5
Y
k=1
(j−k)!(2j)!
j!37079
125096400j2+86356
54729675j+1
28800
−4j−1j!5845j
1990656 +23297
39813120
5
12j−1 7
Y
k=1
(j−k)!4j−1j!38213
1146617856j2+915313
2293235712j−1940327
53508833280
−(2j)!
j!211033
2319969600j2+8139013
71455063680j+1
887040
6
12j−1 9
Y
k=1
(j−k)!(2j)!
j!5004682489
7527663360360000j3+7523688218141
491807339543520000j2
+20903746897
3944978659440000j+691
19813248000
−4j−1j!44274265
3632485367808j2+135152437
3632485367808j
−522404797
77052719923200
7
12j−1 11
Y
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 first 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.
摘要：

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：29 页 大小：841.64KB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 29
评分 收藏
分享
立即下载
客服
关注