7
$\begingroup$

Consider the standard embedded $n$-cross polytope $P_n$ with vertices $\pm e_i \in \mathbb R^n$. Let us consider decompositions of this polytope into $2^{n-1}$ simplices, such that these simplices have only vertices that are also vertices of $P_n$. How many different such decompositions exist? (Note that such a decomposition is not necessarily a triangulation.)

Secondly, I want to know the same about the $n$-polytope $Q_n$ which is defined to be the convex hull of the set $\{e_i+e_j \in \mathbb R^{n+1} \ | \ 1 \leq i < j \leq n+1\}$. (Think about $Q_n$ as a $n$-simplex which is twice as large as usual and has its corners removed.)

$\endgroup$
0
9
$\begingroup$

The cross-polytope has $2n$ vertices in $n$ antipodal pairs. A simplex with $n+1$ points from these must contain exactly one antipodal pair of points, since if it contains more than one, it has a square face and $0$ volume. So, the simplex is the union of two adjacent cones over facets, or the intersection of the cross-polytope with two adjacent orthants. This means a division of the cross-polytope into $2^{n-1}$ simplices corresponds to a perfect matching of the dual hypercube. These are counted by A005271. The first $7$ values are known. The number increases extremely rapidly, doubly exponentially, since one lower bound is $2^{2^{n-2}}$ (matchings contained in $2^{n-2}$ parallel squares) and one upper bound is $n^{2^{n-1}} = 2^{(\log_2 n) 2^{n-1}}$ (choose a direction for each odd vertex of the cube).

$\endgroup$
0
$\begingroup$

Edit: This doesn't answer the question the poster is asking about decompositions.

The $n$-dimensional cross-polytope $P_n$ can be triangulated (divided into simplices, without adding vertices) in exactly $n$ different ways. Each of these has $2^{n-1}$ simplices.

A quick google search finds Example 6.3.14 in the book "Triangulations: Structures for Algorithms and Applications". They don't give a proof (and they have a typo, I think). This fact is also mentioned without proof in Example 4.9 of the paper "Splitting polytopes". Anyway, this seems to be a "standard fact".

Much less seems to be known about the triangulations of $Q_n$, the "rectified $n$-simplex".

$\endgroup$
4
  • 2
    $\begingroup$ "Divided into simplices, without adding vertices" is not enough to specify "triangulated", since it doesn't exclude decompositions where faces don't meet full faces (e.g., take the triangulation of the octahedron into two pairs of tetrahedra, each pair forming a square pyramid, and rotate by a quarter-turn one of the pyramids). Decompositions of the kind "divided into simplices, without adding vertices" are more numerous. $\endgroup$ – Yoav Kallus Apr 16 '15 at 15:50
  • $\begingroup$ Good point. I missed that. I will ask the original poster which kind of decomposition they actually wanted. $\endgroup$ – Sam Nead Apr 16 '15 at 20:02
  • $\begingroup$ I actually meant all decompositions, not just triangulations. And I am more interested in the second than in the first example. $\endgroup$ – Jens Reinhold Apr 17 '15 at 6:12
  • $\begingroup$ Ok. I edited your question to make that clear, and fixed a typo. I'll leave my non-answer here just in case it helps anybody. $\endgroup$ – Sam Nead Apr 17 '15 at 16:15

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.