The Flip-Graph of the 4-Dimensional Cube is Connected
- PDF / 335,455 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 75 Downloads / 171 Views
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 significantly more complicated. The first nonregular 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 efficient 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:10.1007/s00454-013-9488-y) contains supplementary material, which is available to authorized users. L. Pournin (B) EFREI, 30–32 avenue de la République, 94800 Villejuif, France e-mail: [email protected] L. Pournin École Polytechnique Fédérale de Lausanne (EPFL), 1015 Lausanne, Switzerland e-mail: [email protected]
123
512
Discrete Comput Geom (2013) 49:511–530
the flip-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 identified hereafter with the polytope [0, 1]4 and its vertices with the elements of {0, 1}4 . It is proven in this paper that the flip-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 done using TOPCOM [10]. The proof consists in finding paths in the flip-graph of {0, 1}4 from any triangulation to a corner-cut triangulation [2]. To this end, one needs to perform a sequence of flips that introduces new corner simplices in a triangulation T of {0, 1}4 . Consider the 3-dimensional triangulation U obtained intersecting T with a hyperplane that cuts the corner of [0, 1]4 with apex x. As will be shown below, one can choose x so that, up to an isometry, U belongs to a well characterized set of 1,588 triangulations. In addition, conditions will be given such th
Data Loading...
