# Triangulations of polyhedra

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.

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

• 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. – Igor Pak Nov 13 '10 at 1:13
• See Edelman and Reiner, The higher Stasheff-Tamari posets. Mathematika 43 (1996), no. 1, 127–154. – Hugh Thomas supports Monica Nov 22 '10 at 0:24
• @ H Thomas: Very interesting paper, thanks, that's exactly the kind of thing was asking about! – Dr Shello Dec 6 '10 at 3:25