12
$\begingroup$

I wonder if this question has been considered before and if anything is known. My search attempts have failed so far.

Let's consider the n-dimesnional cube, $[0,1]^n$, and let's call a simplex with vertices in $\{0,1\}^n$, nice if it has volume $\frac{1}{n!}$. How many triangulations does the unit cube have into nice simplices?

$\endgroup$
  • $\begingroup$ Do nice simplices have nice faces? Or are such simplices extra nice? It seems to me that the extra nice decompositions may admit an easier path to enumeration. Gerhard "Try Being Extra Nice Today" Paseman, 2014.12.13 $\endgroup$ – Gerhard Paseman Dec 14 '14 at 4:59
  • 5
    $\begingroup$ Nice means "unimodular" in your case; you look for the number of unimodular triangulations. $\endgroup$ – Per Alexandersson Dec 14 '14 at 9:30
  • $\begingroup$ The volume of a simplex with integer vertices is an integer multiple of 1/n!, so a triangulation of the n cube is nice if and only if it is made by n! (non-degenerate) simplices. $\endgroup$ – Pietro Majer Dec 14 '14 at 16:41
  • 1
    $\begingroup$ By triangulation, do you mean that the simplices have to meet face-to-face, or just any partition of the hypercube into simplices? $\endgroup$ – David Eppstein Dec 14 '14 at 20:10
  • 1
    $\begingroup$ @DavidEppstein For the context in which this question came up, we were considering arbitrary partitions of the hypercube into simplices. However, both questions sound interesting. $\endgroup$ – Gjergji Zaimi Dec 14 '14 at 22:50
4
$\begingroup$

This is not my answer originally (see comments above) so I'm making it community wiki. Just among pulled triangulations of the 3-cube (that is, triangulations formed by choosing a vertex, triangulating the squares of the cube that do not touch this vertex, and connecting each of these triangles to the chosen vertex) there are eight choices of vertex to pull, and eight choices of how to triangulate. As TheMaskedAvenger has described, these may also be described by partitioning the cube into three square pyramids and then triangulating each pyramid in one of two ways, as shown below.

Pulled triangulations of the cube

There are 60 of these pulled triangulations, not 64, because for each chosen vertex one of the triangulations is the same as one where the opposite vertex is chosen.

There are also 12 more triangulations of the 3-cube that are a little trickier to describe. Choose one of the four triangulations that are pulled from two opposite vertices. Then, choose two opposite square faces of the cube, merge the two tetrahedra that touch that face, and split the resulting two pyramids in the other way. So altogether the cube has at least 72 triangulations.

In 4d, you can then do a pulling triangulation again, choosing one of these 72 triangulations in each of the four 3-cube facets that are opposite the chosen vertex. You can't choose them independently (if we're forming triangulations rather than partitions) because the diagonals have to match on the squares connecting these 3-cubes. Even so the number of possible triangulations seems to grows very quickly with the dimension...

$\endgroup$
  • $\begingroup$ So in dimension n we can fix a pulled partition from a vertex V (= by simplices all having V as a vertex) exactly by defining a triangulation of the bouquet of n facets of the cube around the vertex opposite to V. $\endgroup$ – Pietro Majer Dec 15 '14 at 8:16
  • $\begingroup$ Also, we can fix an "axial" triangulation (= all simplices have two opposite vertices V, V' in common, that is a diagonal of the cube as a common edge) fixing a n-2 dimensional triangulation on the union of all those n-2 dimensional faces of the cube, that do not have neither V nor V' as vertex. These are n(n-1) (just one half of the total number 2n(n-1) of n-2 dimensional faces of $I^n$). $\endgroup$ – Pietro Majer Dec 15 '14 at 8:21
  • $\begingroup$ So I guess there is a lower bound of the form $$A(n)\ge 2^nB(n-1)-2^{n-1}C(n-2)$$ where A(n) B(n) C(n) count the number of (nice, pulled) triangulations, respectively on the n-cube, on a bouquet of n+1 n-cubes, on a complex of (n+1)(n+2) n-cubes, as described above. $\endgroup$ – Pietro Majer Dec 15 '14 at 8:27
4
$\begingroup$

Finding the exact number of unimodular triangulations of a cube in higher dimension is, I would say, out of reach. In fact, I would say the number is doubly exponential in n (that is, exponential in the number of vertices). [Update: see my other answer for a doubly exponential lower bound]

For dimension 3 I can reproduce David's count of 72 in a different fashion:

Every unimodular triangulation of the 3-cube uses one (and only one) of the four diameters of the cube. So, it suffices to count the triangulations that use one particular diameter. For this do the following: if you project the cube along the direction of the diameter used, you see a hexagon. The vertices to which the diameter is joined in your triangulation must form a sub polygon of this hexagon with the center inside. There are 18 possibilities:

  • the whole hexagon.
  • the six pentagons that you obtain leaving out one vertex of the hexagon.
  • the nine quadrilaterals that you get leaving out two non-consecutive vertices.
  • the two triangles that you get using alternate vertices.

You need to check that all possibilities do indeed extend to triangulations of the cube (so far we have only described the "star" of the diameter used) and that no possibility extends in two ways. Once you check this (there are 5 combinatorially different cases to understand) you will have proved that there are 18 triangulations using that diameter, and 72 in total.

$\endgroup$
3
$\begingroup$

Here is a lower bound of $2^{\Omega(2^n)}$ for the number of unimodular triangulations.

Let me start with the triangulation described by Włodzimierz Holsztyński, which is indeed quite classical and I will call the standard triangulation of the $n$-cube. Its $n$-simplices have as vertices the $n!$ monotone paths of vertices from $(0,\dots,0)$ to $(1,\dots,1)$.

Observe that the standard triangulation $T$ has the following property: for each $2$-face of the cube, the two triangles in which $T$ divides that face have the same link (that is, they are joined to the same simplices). This implies we can perform a flip on that $2$-face: we can remove the two triangles in it together with all simplices containing them, and insert the other triangulation of the quadrilateral, with the same link as the old one had. (This is a higher dimensional analogue of changing the triangulation in a square pyramid, as described in David Eppstein's or TMA's answers)

Now, if we find $k$ of these $2$-faces in which we can perform flips independently (that is, if no two of the flips affect a common simplex) then we get $2^k$ triangulations of the cube. One way to guarantee that the flips are independent is to use $2$-faces at the same level, by which I mean the following: every $2$-face is defined by $n-2$ equalities of the form $x_i=\epsilon_i$, where $\epsilon_i\in \{0,1\}$. I say a $2$-face has level $l$ if exactly $l$ of the $\epsilon$'s are equal to $1$.

The number of $2$-faces at level $l$ is ${n \choose n-2}{n-2 \choose l}$ which, for $l\sim (n-2)/2$, grows as $2^n n^{3/2}$ (modulo a constant). Thus, we have at least $$ 2^{\Omega(2^n n^{3/2})} $$ unimodular triangulations of the $n$-cube.

It is also easy to give a crude upper bound that is not that far from the lower bound. Observe that a unimodular triangulation is a set of $n!$ $n$-simplices taken out from a total of (at most) $2^n \choose n+1$ $n$-simplices. Thus, the number of unimodular triangulations (or, of all triangulations, for that matter) is at most $$ {{2^n \choose n+1} \choose n!} \le 2^{O(n^{n+2})} $$

$\endgroup$
-4
$\begingroup$

There are at least $\ 2^{n-1}\ $ triangulations of $\ [0;1]^n\ $ into nice $n$-simplexes. I am quite sure that there are exactly $\ 2^{n-1}\ $ of them.

CONSTRUCTION   First I'll present one nice triangulation of $\ [0;1]^n$.

NOTE   Włodzimerz Kuperberg and myself have obtained this nice triangulation (see below; but of course we didn't use term nice) independently. I did it during the first half of 1996 (I don't know Włodek K's exact date). Looking back, it is closely related to the old homological/combinatorial triangulation of a prism (one may check for example a Pontryagin's small monograph on Combinatorial Topology; see Лев Семёнович Понтря́гин); small but great.

Let $\ \pi:\{1 \ldots n\}\rightarrow \{1 \ldots n \}\ $ be an arbitrary permutation. Let

$$\Delta_{\pi}\ :=\ \{(x_1\ldots x_n)\in [0;1]^n\ :\ \forall_{k=2}^n\ x_{\pi(k-1)}\le x_{\pi(x_k)}\} $$

The family of $n$-simplexes $\ \Delta_{\pi} : \pi\in S_n,\ $ together with their simplicial faces, forms a nice triangulation (which has $\ n!\ $ simplexes of dimension $\ n.\ $ We get the $\ 2^{n-1}\ $ such triangulations due to the $\ \mathbb Z_2^n\ $ action of isometries on $\ [0;1]^n$.

I feel that there are no other nice triangulations in $\ [0;1]^n$.


The example below was written by David Eppstein, and it was conceived mostly by The Mask Avenger:

COUNTEREXAMPLE (Yes!) in dimension 3   If you see a counterexample in dimension $\ 3\ $ then here is a place to write down a $5$-th nice triangulation (just replace each star by a real number)--here simplexes are specified by their vertices:

  1. simplex:   $((0\ 0\ 0)\ \ (1\ 0\ 0)\ \ (1\ 1\ 0)\ \ (1\ 0\ 1))$
  2. simplex:   $((0\ 0\ 0)\ \ (1\ 1\ 1)\ \ (1\ 0\ 1)\ \ (1\ 1\ 0))$
  3. simplex:   $((0\ 0\ 0)\ \ (0\ 1\ 0)\ \ (1\ 1\ 0)\ \ (0\ 1\ 1))$
  4. simplex:   $((0\ 0\ 0)\ \ (1\ 1\ 1)\ \ (0\ 1\ 1)\ \ (1\ 1\ 0))$
  5. simplex:   $((0\ 0\ 0)\ \ (0\ 0\ 1)\ \ (1\ 0\ 1)\ \ (0\ 1\ 1))$
  6. simplex:   $((0\ 0\ 1)\ \ (1\ 1\ 1)\ \ (0\ 1\ 1)\ \ (1\ 0\ 1))$

Of course a picture can be nicer and (almost :-) as good.


From wh again:

@GjergjiZaimi -- thank you for your Question. Then, The Masked Avenge, David Eppstein and Pietro Majer--thank you for your solutions and comments; and all of you: TMA, David, and Pietro--for your patient dealing with my difficulties.

$\endgroup$
  • 2
    $\begingroup$ For instance, among the $T(n)$ nice triangulations of the $n$-cube, exactly $T(n-1)^n$ are made by simplices all having $(0,0,\dots,0)$ as a common vertex. $\endgroup$ – Pietro Majer Dec 14 '14 at 17:17
  • 2
    $\begingroup$ Suppose I divide the cube into three congruent right angled pyramids sharing a common vertex. Each of these pyramids can be decomposed into two simplices in at least two ways. I thus have 8 different decompositions of the cube into simplices, 64 if I vary the common apex. Which of these decompositions is not a triangulation? $\endgroup$ – The Masked Avenger Dec 15 '14 at 4:28
  • 3
    $\begingroup$ Wlod: here's my description of TMA's construction. Connect one vertex to the three opposite faces of a cube, forming three (skewed) square pyramids. Each pyramid can be divided into two orthoschemes (the convex hull of a right-angled-path) or it can be divided into an equilateral-triangle pyramid (the convex hull of a right-angled $K_{1,3}$) and another nice tetrahedron (congruent to the tet with vertices 000 111 110 101). So there are indeed two distinct possibilities per pyramid, eight per pyramid-decomposition, and 48 total among triangulations of this type. $\endgroup$ – David Eppstein Dec 15 '14 at 6:10
  • 2
    $\begingroup$ It seems challenging to communicate this idea effectively to you. $\endgroup$ – The Masked Avenger Dec 15 '14 at 7:21
  • 2
    $\begingroup$ I'll just leave this here: meta.mathoverflow.net/questions/1987/politeness-on-mo-metamo $\endgroup$ – Daniel Soltész Dec 15 '14 at 7:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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