13
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Mar 6, 2021 at 16:59

3 Answers 3

Reset to default
21
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ A slightly newer version is here math.ucdavis.edu/~deloera/BOOK/final.pdf $\endgroup$
    – j.c.
    Commented Nov 12, 2010 at 20:09
  • $\begingroup$ Both of those links are broken! $\endgroup$
    – amI
    Commented Jan 3, 2018 at 19:42
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .