16
$\begingroup$

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$.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ 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 $\endgroup$
    – Ian Agol
    May 23, 2013 at 2:04
  • $\begingroup$ 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$? $\endgroup$
    – Matthew Kahle
    Jun 12, 2013 at 7:36
  • 1
    $\begingroup$ 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] $\endgroup$
    – BS.
    Aug 9, 2013 at 11:52
  • 1
    $\begingroup$ [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). $\endgroup$
    – BS.
    Aug 9, 2013 at 11:58
  • 1
    $\begingroup$ [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. $\endgroup$
    – BS.
    Aug 9, 2013 at 12:19

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Matthew Kahle
    May 24, 2013 at 16:26
8
$\begingroup$

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:

   TriangulationsTorusCounts
* = also generated by edge flipping
Many of the counts were computed by the software surftri.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.