# Triangulating hypercubes

Motivation: I'm working on a computational problem at the moment, and have some very good routines for natively working with simplicial complexes and calculating homology, but the structures I'm dealing with arise naturally as cubical complexes.

Problem: Is there an efficient way to triangulate the n-cube, i.e. calculate a (relatively) small list of n-simplices on the same vertices as the cube, and which define a simplicial complex spanning the cube?

I've done some reference-chasing and there seems to be no decently-sharp estimate (as an upper or lower bound) for the asymptotic complexity of the problem, although the best upper-bounds I'm aware of (for the size of the smallest solution-set) seem to indicate something exponentially smaller than factorial (see Haiman, 91). This paper also exhibits a lower bound, given below

$\frac{2^n\,n!}{(n+1)^{{}^{(n+1)/2}}}$

Orden and Santos improved the upper bound somewhat, by reducing the base of the exponential.

-
See also "Simplexity of the $n$-cube" at The Open Problems Garden: garden.irmacs.sfu.ca/?q=op/simplexity_of_the_cube –  Joseph O'Rourke Feb 10 '11 at 16:54

For the question as stated, it's a big open problem to triangulate the $n$-cube, and the papers that you cite are basically the state of the art. The lower bound that you give is simply a matter of comparing the volume of an $n$-cube to the volume of the largest possible $n$-simplex inside it, only with the extra idea due to Warren Smith to work in hyperbolic geometry rather than in Euclidean geometry. As you should notice, this lower bound is exponential, while all of the upper bounds are factorial. The upper bound comes from the following simple idea of Haiman: Suppose that you have good triangulations of some low-dimensional cubes. Then you can take their Cartesian product and use the standard step triangulation of a product of simplices. Using for example the triangulation of a 3-cube with 5 simplices instead of the usual 6, this immediately gives you a small exponential gain over the $n!$ answer using the standard step triangulation. Orden and Santos offer a slight improvement of Haiman's idea.

Combinatorialists take this summary of results as an invitation to do better. The upper and lower bounds are very far apart.

If your ultimate goal is to compute homology in high dimensions, then you are much better off NOT triangulating the cubes. It is computationally superior to make chain complexes directly from the cubical complex, and then use the same integer linear algebra that you would have used otherwise.

-
The combinatorialists do not seem to have made much progress. The last real advance in the field is Warren Smith's thesis (which was in 1988, if I recall). The problem (known as "the simplexity of the cube") has been around for a very long time, though I don't know the whole history. –  Igor Rivin Feb 10 '11 at 16:38

A slight improvement on the lower bound was recently obtained by Alexey Glazyrin (http://arxiv.org/abs/0910.4200, http://www.sciencedirect.com/science/article/pii/S0012365X12003974). Basically, it changes the $2^n$ factor in Nick's initial post to an $e^n$. Smith's hyperbolic volume method gave an $\sqrt{6}^n$.

But, of course, as Greg points out, the real open question is whether the simplicity of the cube grows as the $c^n n!/n^{n/2}$ of the lower bounds or as the $c^n n!$ that can be achieved by actual constructions (or something in between).

-

In case it is helpful for your computational problem, note that the freely available software CHomP will compute homology of cubical complexes.

http://chomp.rutgers.edu/

-
Cubical complexes in general, or just subcollections of the standard tiling of Euclidean space by unit cubes? It looks like the latter to me. –  Greg Kuperberg Feb 10 '11 at 16:49
Awesome, thank you! I've been trying in HAP(GAP package), but it's not too happy (so far as I can tell) if I'm not working with a complex where each cube sits inside a cube of maximal dimension, the so-called "pure" complexes. So I can't just start sticking extra squares hanging off my cubes, say. –  Nick Loughlin Feb 11 '11 at 11:11
I didn't notice Greg's comment, which would suggest that my last post was off-the-mark, although I will check it out. –  Nick Loughlin Feb 11 '11 at 11:12

If you think of the $n$-cube as unordered sequences of points from $[0,1]$, and the $n$-symplex as an ordered sequence of points from $[0,1]$, then it is easy to see how to decompose the $n$-cube into $n!$ simplices each of hyper-volume $1/n!$. I am not sure that this is a triangulation --- no opinion at this writing, but if not, then try subdivision.

-
Yes, this and some related triangulations are known - a slightly better version (in 3d gives 5 simplices instead of 6) is to 2-colour the vertices and dissect-off a simplex at each odd vertex, say, and then deal with the polytope you're left with - see theorem 3.6.3 here: books.google.com/books?id=SxY1Xrr12DwC&pg=PA315 –  Nick Loughlin Feb 10 '11 at 13:20
5 simplices is sharp in three dimensions, since if you take the regular ideal cube, you will see that the simplices it is subdivided in are regular also. –  Igor Rivin Feb 10 '11 at 16:36
Of course, "ideal" means ideal in hyperbolic 3-space. Do other geometries in higher dimensions give worse estimates? –  Douglas Zare Feb 10 '11 at 17:14