Math-2088 · mathematics · Combinatorics

Math-2088

What is the minimum number of n-simplexes needed to triangulate the n-cube

Status Open · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedOpenOpen

Statement

Definitions and mathematical statement

Let $Q_n=[0,1]^n$ and let its vertex set be $\{0,1\}^n$. A vertex triangulation of $Q_n$ is a finite collection of nondegenerate $n$-simplices whose vertices belong to $\{0,1\}^n$, whose union is $Q_n$, and such that the intersection of any two simplices is either empty or a common face of both. In particular, their interiors are disjoint. Lower-dimensional faces are included implicitly in the resulting simplicial complex.

Define the simplexity in this convention by \[ t(n)=\min\{\text{number of full-dimensional simplices in such a triangulation}\}. \] Determine $t(n)$, or obtain asymptotically sharp bounds as $n\to\infty$. The usual triangulation obtained by ordering the coordinates shows $t(n)\le n!$, but it need not be optimal.

The corner restriction excludes added Steiner vertices, and the common-face condition excludes arbitrary simplicial dissections with incompatible subdivisions across interfaces. These are different minimization problems, even when useful bounds compare them. Counting refers only to $n$-dimensional simplices, not to all faces in the complex. An upper bound requires an actual compatible triangulation covering the cube, while a lower bound must apply to every such triangulation, irrespective of symmetry or regularity.

Short English statement

Determine the minimum number of n-simplices in a triangulation of the n-cube using only cube vertices.

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.