Content area
Full Text
Discrete Comput Geom (2013) 49:511530 DOI 10.1007/s00454-013-9488-y
The Flip-Graph of the 4-Dimensional Cube is Connected
Lionel Pournin
Received: 30 January 2012 / Revised: 26 July 2012 / Accepted: 11 February 2013 / Published online: 19 March 2013 Springer Science+Business Media New York 2013
Abstract Flip-graph connectedness is established here for the vertex set of the 4-dimensional cube. It is found as a consequence that this vertex set has 92,487,256 triangulations, partitioned into 247,451 symmetry classes.
Keywords 4-Dimensional hypercube Tesseract Flip-graph connectivity
Triangulations Enumeration TOPCOM k-Regularity
1 Introduction
It is well known that the vertex set of the 3-dimensional cube has exactly 74 triangulations, all regular, partitioned into 6 symmetry classes [1,2]. The case of the 4-dimensional cube turns out to be signicantly more complicated. The rst non-regular triangulation of its vertex set has been found almost two decades ago [1], and the total number of such triangulations was, up to now, unknown. Prior work [5] provided all the regular triangulations and TOPCOM [10] made it possible to conjecture the number of the non-regular ones, already several years ago. This conjecture is shown here to be true. Indeed, the only triangulation enumeration method efcient enough to be tractable in the case of the 4-dimensional cube actually consists in exploring
Electronic supplementary material The online version of this article (doi:http://dx.doi.org/10.1007/s00454-013-9488-y
Web End =10.1007/s00454-013-9488-y ) contains supplementary material, which is available to authorized users.
L. Pournin (B)
EFREI, 3032 avenue de la Rpublique, 94800 Villejuif, France e-mail: [email protected]
L. Pournincole Polytechnique Fdrale de Lausanne (EPFL), 1015 Lausanne, Switzerland e-mail: [email protected]
123
512 Discrete Comput Geom (2013) 49:511530
the ip-graph of its vertex set [2]. In this perspective, completely enumerating the triangulations of the vertex set of the 4-dimensional cube is a task conditioned to the connectedness of this graph, which remained an open problem until now [2].
The 4-dimensional cube is identied hereafter with the polytope [0, 1]4 and its ver
tices with the elements of {0, 1}4. It is proven in this paper that the ip-graph of {0, 1}4
is connected. It is found as a consequence, that the vertex set of the 4-dimensional cube has 92,487,256 triangulations, partitioned into 247,451 symmetry classes. Some of the results in the paper require computer assistance. These computations were mostly...