Growth constants of the classes of planar maps

edit · history · discussion · files · short url · combinatorics generating function

Numbers

class

size

labelling

$\gamma$

all rooted planar maps

number of edges

unlabelled:

comment: Loops and multiple edges are allowed. Tutte's count gives $\gamma=12$ [1].

2-connected rooted planar maps

number of edges

unlabelled:

27/4

comment: Nonseparable maps have no loops or cut vertices; multiple edges are allowed. The constant is exactly $27/4$ [1].

3-connected rooted planar maps

number of edges

unlabelled:

comment: The underlying graph is simple and 3-vertex-connected. The constant is exactly $4$ [1].

bipartite rooted planar maps

number of edges

unlabelled:

comment: The underlying graph is bipartite; no choice of a colouring is counted. The constant is exactly $8$ [1].

Eulerian rooted planar maps

number of edges

unlabelled:

comment: Every vertex has even degree, with each loop contributing $2$. Planar duality identifies these counts with bipartite-map counts [2].

loopless rooted planar maps

number of edges

unlabelled:

256/27

comment: Loops are forbidden and multiple edges are allowed. The constant is exactly $256/27$ [2].

type I triangulations

number of vertices

unlabelled:

20.78460969082652752232935609807046840331366304572456753666968375342319620290560044497375424108698291

comment: Type I allows loops and multiple edges. The exact constant is $12\sqrt3$, stored as a certified real enclosure [3].

type II triangulations

number of vertices

unlabelled:

27/2

comment: Type II forbids loops and allows multiple edges. The constant is exactly $27/2$ [4].

type III triangulations

number of vertices

unlabelled:

256/27

comment: Type III is simple, with neither loops nor multiple edges. The constant is exactly $256/27$ [4].

quadrangulations

number of faces

unlabelled:

comment: Every face has degree $4$, with repeated boundary edges counted with multiplicity. Tutte's angular bijection gives the same count as all maps with $n$ edges [3].

simple quadrangulations

number of faces

unlabelled:

27/4

comment: The underlying graph is simple. The ternary-tree parametrisation of the counting series gives $\gamma=27/4$ [5].

Definition

The growth constant of a class of rooted planar maps is $\gamma=\lim_{n\to\infty}c_n^{1/n}=1/\rho$, where $c_n$ counts unlabelled maps of size $n$ and $\rho$ is the radius of convergence of their ordinary generating function [1]. Size specifies the counting convention for the common quantity $\gamma$.

Parameters

class

— map class (a class of rooted planar maps)

size

— size statistic (the statistic counted by the ordinary generating function)

labelling

— labelling convention (unlabelled rooted maps)

Formulas

(1)

A triangulation with $v$ vertices has $3v-6$ edges and $2v-4$ faces; a quadrangulation with $f$ faces has $2f$ edges and $f+2$ vertices. These identities follow from Euler's formula and counting edge incidences along face boundaries.

(2)

For $n\geq2$, the numbers of arbitrary, 2-connected, bipartite and loopless rooted maps with $n$ edges are respectively $a_n=\frac{2\,3^n(2n)!}{n!(n+2)!}$, $b_n=\frac{2(3n-3)!}{n!(2n-1)!}$, $e_n=\frac{3\,2^{n-1}(2n)!}{n!(n+2)!}$ and $\ell_n=\frac{2(4n+1)!}{(n+1)!(3n+2)!}$. Eulerian maps have count $e_n$ [1] [2].

(3)

For $n\geq1$, let $t_n^{(i)}$ count type $i$ triangulations with $n+2$ vertices. Then $t_n^{(I)}=\frac{2\,4^n(3n)!!}{(n+1)!(n+2)!!}$, $t_n^{(II)}=\frac{2^{n+1}(3n)!}{n!(2n+2)!}$ and $t_n^{(III)}=\frac{2(4n-3)!}{n!(3n-1)!}$, where $m!!$ is the product of the positive integers at most $m$ having the same parity as $m$ [3] [4] [5].

(4)

If $Q_n$ and $q_n$ count all and simple quadrangulations with $n$ faces, respectively, then $Q_n=a_n$ and $q_n=b_n$ for $n\geq2$. Equivalently, $q(z)=\sum_{n\geq2}q_nz^n=z(\alpha-1)(2-\alpha)$, where $\alpha=1+z\alpha^3$ and $\alpha(0)=1$ [3] [5].

(5)

Let $B(z)=\sum_{n\geq2}b_nz^n$, $D(z)=B(z)/z$ and let $F$ be the compositional inverse of $D$ at $0$. The generating function $T(z)$ for 3-connected rooted maps counted by edges satisfies $T(z)=z\left(z-\frac{2z^2}{1+z}-F(z)\right)$. The parametrisation $z=u(1-u)^2$, $B(z)=u^2(1-2u)$ gives $D(z)=\frac{u(1-2u)}{(1-u)^2}$; its inverse has discriminant $1-4z$, yielding the growth constant $4$ [1].

(6)

The exact count ratios give $\gamma_{\mathrm{all}}=12$, $\gamma_{\mathrm{2-connected}}=27/4$, $\gamma_{\mathrm{bipartite}}=\gamma_{\mathrm{eulerian}}=8$, $\gamma_{\mathrm{loopless}}=256/27$, and $\gamma_{II}=27/2$, $\gamma_{III}=256/27$ for triangulations counted by vertices. For type I, $\lim_{n\to\infty}t_{n+2}^{(I)}/t_n^{(I)}=432$, and the growth constant is the positive square root $\gamma_I=12\sqrt3$ [3].

Comments

(7)

A planar map is an embedding of a finite connected multigraph in the oriented sphere, considered up to orientation-preserving homeomorphisms. A root is a distinguished directed edge. The face on a fixed side of the root is determined by the root, rather than being an additional marked face [6] [2].

(8)

The size $n$ counts all edges for the six general map classes, all vertices for triangulations, and all faces for quadrangulations. No vertices are labelled, so no factorial is divided out of $c_n$. These size conventions give a nonzero count at every sufficiently large integer size. All eleven limits exist by the cited exact enumerations [1] [2] [4] [3] [5].

(9)

A 2-connected map has at least two edges, no loops and no cut vertex; the digon is included. A 3-connected map has a simple underlying graph with at least four vertices that remains connected after deletion of any two or fewer vertices. Bipartite maps have bipartite underlying graphs, with no colouring counted as additional data. Eulerian maps have even degree at every vertex, counting a loop twice. Loopless maps allow parallel edges [1] [2].

(10)

A triangulation has every face of degree $3$, and a quadrangulation has every face of degree $4$. Face degree counts edge incidences along the boundary, including repeated incidences. Type I triangulations allow loops and parallel edges, type II forbids loops, and type III forbids both. A simple quadrangulation has neither loops nor parallel edges [4] [7] [5].

(11)

Planar duality gives a bijection between Eulerian and bipartite maps, preserving the number of edges [2]. Tutte's angular bijection identifies arbitrary maps with $n$ edges and quadrangulations with $n$ faces [3].

(12)

Tree growth constants use the same asymptotic notion. A map retains its embedding in the sphere; enumeration of abstract planar graphs counts different objects. Growth constants of the classes of planar graphs uses exponential generating functions for labelled abstract graphs counted by vertices.

Programs

(P1)

Sage

import numberdb.sage as numberdb
from sage.rings.real_arb import RealBallField
B = RealBallField(numberdb.bits(100, losing=64))
12 * B(3).sqrt()

References

[1]

M. Noy, C. Requilé and J. Rué, Enumeration of rooted 3-connected bipartite planar maps, Comptes Rendus Mathématique 362 (2024), 143–158. Introduction. (arXiv) (doi)

[2]

V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Mathematics 36 (2006), 364–387. Sections 0 and 4. (doi)

[3]

N. Curien and J.-F. Le Gall, First-passage percolation and local modifications of distances in random triangulations, Annales scientifiques de l’École Normale Supérieure 52 (2019), 631–701. Introduction and Section 2.1. (doi)

[4]

O. Angel and O. Schramm, Uniform Infinite Planar Triangulations, Communications in Mathematical Physics 241 (2003), 191–213. Definitions 1.2–1.3, Theorem 2.1 and Proposition 2.2. (arXiv) (doi)

[5]

M. Albenque, É. Fusy and D. Poulalhon, On symmetric quadrangulations and triangulations. Sections 3.1–3.2. (arXiv) (doi)

Links

[6]

Noy, Requilé and Rué: full text

[7]

Curien and Le Gall: full text

Similar tables

Tree growth constants — growth constants for tree classes, with the same ordinary or exponential generating function distinction

Growth constants of the classes of planar graphs — growth constants for labelled abstract planar graphs counted by vertices, with exponential generating functions

Data properties

Entries are of type: real number

How well the digits are known: proven

How they were obtained:

Ten entries are exact integers or rationals obtained from published enumeration formulas. The type I triangulation constant is exactly $12\sqrt3$ and is stored as a 100-significant-digit Arb enclosure. The working precision is numberdb.bits(100, losing=64); its computed radius is less than $10^{-115}$. Exact rational evaluation verifies that the endpoints represented by the stored decimal bracket the positive root of $x^2-432$. A second calculation at 150 digits gives an agreement check.

The attached checks derive limiting count ratios symbolically, compare 80 consecutive ratios for every factorial formula, test 80 type I two-step ratios, and verify formal generating function identities through degree 44. They independently enumerate connected planar rotation systems with one through four edges, with the one-edge maps and Catalan tree counts as controls. The same checks compare every value read back from the draft to independently derived constants. The simple-quadrangulation factorial formula in the cited preprint has a one-face indexing shift; its displayed series and parametrisation agree with the total-face convention used here, as detailed in source-notes.md.

Table is complete: no (it holds the eleven classical rooted classes covering unrestricted maps, connectivity, parity, absence of loops, types I–III of triangulations, and general and simple quadrangulations; it does not cover every restriction on planar maps)