Lionel Pournin - The 4-dimensional cube









The square is the 2-dimensional analog of the cube. As can be seen on the right, a square can be triangulated in two ways. These two triangulations are obtained from each other by a flip.

There are 74 ways to triangulate the usual (3-dimensional) cube [1], i.e. to decompose it into a set of tetrahedra that intersect along common faces and whose vertices are also vertices of the cube. These 74 triangulations can be partitioned into 6 symmetry classes [1,2]. All these triangulations are regular and, as a consequence, each of them can be transformed into any other triangulation of the cube by performing a sequence of flips.

What about the 4-dimensional cube? Until recently, the number of its triangulations was unknown. Indeed, the only method fast enough to possibly allow for their enumeration consists in exploring the flip-graph of the 4-dimensional cube, under the assumption that this graph is connected. I proved the connectedness of this graph in [3]. Part of this proof is computer-assisted: Proposition 3 from [3] is obtained using an algorithm you will find several implementations of here.

The number of triangulations of the 4-dimensional cube is found as a consequence using TOPCOM: there are 92 487 256 such triangulations, partitioned into 247 451 symmetry classes. These numbers are reported within sequences A238820 and A238821 in the Online Encyclopedia of Integer Sequences:

dimension 0 1 2 3 4
number of triangulations (A238820) 1 1 2 74 92 487 256
number of symmetry classes (A238821) 1 1 1 6 247 451

These numbers are yet unknown for cubes of dimension larger than 4. It is an interesting problem to find them: after all, they may be thought of as distant relatives of Catalan numbers as they also count the triangulations of a structured set of points.

The two triangulations of a square are related by a flip.

The six triangulations, up to symmetry, of a cube [1].


Nonregular triangulations of products of simplices
J. A. De Loera, Discrete Comput. Geom. 15(3), 253-264 (1996)


Triangulations: structures for algorithms and applications
J. A. De Loera, J. Rambau, F. Santos, Algorithms and Computation in Mathematics 25, Springer (2010)


The flip-graph of the 4-dimensional cube is connected
L. Pournin, Discrete Comput. Geom. 49(3), 511-530 (2013)