# How many triangulations of the genus $g$ surface on $n$ vertices?

By "a triangulation of $X$", I mean a simplicial complex whose geometric realization is homeomorphic to $X$. Tutte showed that the number of combinatorially distinct triangulations $t(n)$ of the $2$-dimensional sphere on $n+3$ vertices is asymptotically given by $$t(n) \approx \frac{1}{16} \sqrt{\frac{3}{2 \pi}}n^{-5/2} \left( \frac{256}{27} \right)^n.$$

What is known about the number of combinatorially distinct triangulations $t(n,g)$ of the genus $g$ surface?

(1) It seems likely to me that for fixed $g$, the growth is still roughly exponential, and maybe even $$t(n,g) = \exp \left( c_1 n + c_2 \log n + c_3 + o(1) \right)$$ for some constants $c_1, c_2, c_3 \in \mathbb{R}$ which only depend on $g$. For example in the case $g=0$, Tutte's result gives that $c_1 = 256 / 27$, $c_2= -5 / 2$, and $c_3 = \log \left( \frac{1}{16} \sqrt{\frac{3}{2 \pi}} \right)$. Is the growth of $T(n,g)$ always exponential in $n$, and if so can we at least compute the base of the exponent $c_1$ for higher $g$?

Updated: The rooted version of this question is answered in the paper: Z.-C. Gao. The number of rooted triangular maps on a surface. Journal of Combinatorial Theory, Series B, 52(2):236 – 249, 1991. For fixed genus $g$, Gao establishes strong results along the lines of the above.

(2) At the other extreme, is anything known about the rate of growth of $t(n,g)$ as $n \to \infty$ if $g \approx cn^2$ for some constant $0 < c< 1/12$?

(3) Finally, let $T(n)$ be the total number of combinatorial types of triangulated surfaces on $n$ vertices. What is the rate of growth of $T(n)$ as $n \to \infty$?

Updated: What I would really like to know is if we can not establish the rate of growth of $T(n)$, is there at least an upper bound of order $$T(n) = n^{o(n)}?$$

Or let $\tilde{T}(n)$ denote the number of labelled triangulated surfaces on $n$ vertices. Is it true that $$\tilde{T}(n) = n^{n+o(n)}?$$

Since $\tilde{T}(n) \le n! T(n)$, the second inequality would follow from the first.

Gao's results give that if we assume that the genus $g$ is bounded, then we get the stronger bound $$T(n) = n^{O(n /\log n),}$$ but I still don't know how to handle $g$ growing with $n$.

-
The number $T(n)$ is related to the number of torsion-free subgroups of $PSL_2(\mathbb{Z})$ of index $6n$. The asymptotics of the number of subgroups of index $n$ has been estimated, so one could get upper and lower bounds on the number of torsion-free subgroups of index $n$. ams.org/mathscinet-getitem?mr=466047 –  Ian Agol May 23 '13 at 2:04
Is it easy to say how exactly $T(n)$ is related to the number of torsion-free subgroups of $PSL_2(\mathbb{Z})$ of index $6n$? –  Matthew Kahle Jun 12 '13 at 7:36
A torsion-free subgroup of finite index of the modular group is the same thing as a connected finite 3-valent graph with a cyclic orientation of edges around each vertex, and a choice of a "root" : a vertex and an edge out of it. This is because of the free product decomposition $Z/2*Z/3$ of the modular group, making it the automorphism group of $T_o$, the infinite trivalent tree with cyclic orientations at each vertex (see Serre's "Trees"). But such an "oriented" 3-valent graph is identified with "fat graph", i.e. a small nghbd of the graph embedded in a closed oriented surface, with [tbc] –  BS. Aug 9 '13 at 11:52
[cont'd] disks as components of the complement ("faces"). By duality, this is equivalent to a rooted triangular map on a closed oriented surface, and it is a true triangulation when the 3-valent graph is simple (no loops or double edges). –  BS. Aug 9 '13 at 11:58
[added] Index $6n$ (torsion-free) subgroups correspond to 3-valent maps with $3n$ edges and $2n$ vertices, and so count (rooted, pseudo-)triangulations with $2n$ triangles. And omitting the root corresponds to counting subgroups up to congugacy. –  BS. Aug 9 '13 at 12:19

This is not an answer, but just a source of data gathered by Thom Sulanke and posted at this link. For example, here is his data for the torus:

Many of the counts were computed by the software surftri.

-

I don't think a nice asymptotic formula like the one you've mentioned from Tutte's work is available for higher $g$ to the best of my understanding; it is entirely possible that someone who regularly deals with such things will come along and show us otherwise.

Meanwhile, the state-of-the-art on counting triangulations of genus $g$ surfaces is the lovely paper "The KP hierarchy, branched covers, and triangulations" of Goulden and Jackson, available here: see Theorem 5.4. There are two obstacles in terms of going from this Theorem to a Tutte-type asymptotic formula:

1. The Goulden-Jackson formula is presented in terms of the face count rather than the vertex count, and
2. As is typical in the field, the formula relies on a recursively defined function $f(n,g)$ where (again) $n$ counts the faces rather than the vertices.

I think 1. is surmountable, but 2. might make things difficult: I have no idea how fast $f(n,g)$ grows, but I am sure various simplifications are possible if you set $g = cn$ in their formula.

-
Thanks for the reference Vidit --- that looks like a good paper to read. By the way, you're absolutely right that (1) is surmountable: if $f$ is the number of faces then $n = f/2 + 2 - 2g$. Maybe (2) is surmountable too, for fixed $g$ at least... –  Matthew Kahle May 24 '13 at 16:26