A topologist came to me with this question, but everything I think should work doesn't.

How many triangulations are there of a polyhedron with n vertices?

By a "triangulation" of a polyhedron P we mean a decomposition of P into 3-simplices whose interiors are disjoint, whose vertices are vertices of P, and whose union is P. Since this obviously depends on the polyhedron, let's say that P is the convex hull of n points on the curve (t, t^2, t^3). (I think this is general, but a proof of that would be nice too.) In particular, this means that all of the faces are triangles, since no four vertices are coplanar.

Since triangulations of a polygon are counted by the Catalan numbers, a reasonable first guess is that these are counted by the generalized Catalan numbers $C_{n,k} = \frac{1}{(k-1)(n+1)} {kn \choose n}$, which count k-ary trees (among other things). But just at n=5 we run into trouble: there are 2 (not 3) such triangulations, and they don't even contain a fixed number of pieces: one of them triangulates P into two tetrahedra, and one breaks it into three.

This seems obvious enough that someone would have asked it before, but I'm not finding anything. Of course, answers to the obvious generalization (triangulations of k-polytopes whose vertices lie on (t, t^2, ..., t^k)) are welcome as well.

  • $\begingroup$ As Pak and O'Rourke point below, the asymptotics of the number of triangulations of cyclic polytopes is more or less known, and covered in my book on Triangulations with de Loera and Rambau. But the original question is about the exact number of triangulations of the cyclic 3-polytope with n vertices. I just want to point out that a nice closed formula for that could exist, although we do not know it. Related to this, I have a paper where we compute the exact number of triangulations of the cyclic d-polytope with d+4 vertices (doi.org/10.1007/s00454-001-0050-y) $\endgroup$ – Francisco Santos 2 days ago

You should read Section 6.1 in the excellent monograph "Triangulations" by De Loera, Rambau and Santos (here is a slightly dated version). It deals with triangulations of cyclic polytopes - exactly the subject of your question. Not only it answers your question, it is also the state of art for the rest of the subject.


Although the answer is provided by Igor's pointers to the Triangulations book, it might be useful to supplement those pointers with the explicit bounds. The lower bound is due to Gil Kalai, and the upper bound to Tamal Dey. For fixed dimension $d$, the cyclic polytope has at least $\Omega( 2^{n^{ \lfloor d/2 \rfloor }})$ triangulations, and for $d$ odd, at most $2^{ O( n^ {\lceil d/2 \rceil} ) }$ triangulations. So, for $d=3$, the case posed in the question, the bounds are between $c^n$ and $c^{n^2}$. See Section 8.4 (pp. 396-398) of Triangulations.


Not an answer, but more questions!

What are the natural orderings on the set of triangulations for fixed $n$? Do any of these posets map naturally to the poset of triangulations of the $n$-gon?

I'm asking because of the well-known relationship between triangulations of n-gons and the Stasheff Associahedron, the later of which relates to far too much to detail here. But relations between this and the 3-d version you ask about would be very interesting.

A related MO question on the Associahedrian and Catalan numbers is here: Combinatorics of the Stasheff polytopes

  • 2
    $\begingroup$ You might want to ask new questions as separate questions (see FAQ). Also, I think you might like to read the section I mentioned above, before asking your question. $\endgroup$ – Igor Pak Nov 13 '10 at 1:13
  • 1
    $\begingroup$ See Edelman and Reiner, The higher Stasheff-Tamari posets. Mathematika 43 (1996), no. 1, 127–154. $\endgroup$ – Hugh Thomas Nov 22 '10 at 0:24
  • $\begingroup$ @ H Thomas: Very interesting paper, thanks, that's exactly the kind of thing was asking about! $\endgroup$ – Dr Shello Dec 6 '10 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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