8
$\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.)

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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).

Improve this answer
$\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".

Improve this answer
$\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, 2015 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, 2015 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, 2015 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, 2015 at 16:15

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.