Ten Problems in Geometry

Abstract

Geometry is a field of knowledge, but it is at the same time an active field of research—our understanding of space, about shapes, about geometric structures develops in a lively dialogue, where problems arise, new questions are asked every day. Some of the problems are settled nearly immediately, some of them need years of careful study by many authors, still others remain as challenges for decades. In this chapter, we describe ten problems waiting to be solved.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Geometry is a field of knowledge, but it is at the same time an active field of research—our understanding of space, about shapes, about geometric structures develops in a lively dialogue, where problems arise, new questions are asked every day. Some of the problems are settled nearly immediately, some of them need years of careful study by many authors, still others remain as challenges for decades. In this chapter, we describe ten problems waiting to be solved.

Unfolding Polytopes

Albrecht Dürer’s famous geometry masterpiece “Underweysung der Messung mit dem Zirckel und Richtscheyt” was published in Nuremberg in 1525. The fourth part of this book contains many drawings of nets of 3-dimensional polytopes and, implicitly, the following conjecture:

Every 3-dimensional convex polytope can be cut open along a spanning tree of its graph and then unfolded into the plane without creating overlaps.

This conjecture was posed explicitly by the British mathematician Geoffrey C. Shephard in 1975. It has captured many geometers’ attention since then—and led to many interesting results and insights in this area, many of them described in Chapter 6 in this book.

One important insight is that the spanning tree must be chosen with care. Given any polytope, it is easy to find some spanning tree in its graph. After cutting the boundary along the edges of this tree, there is a unique way to unfold it into a planar figure. However, the problem is that overlaps could occur, and indeed they do occur. Figure 22.1a shows a prism, once cut open along a good spanning tree, once cut open along a bad spanning tree. Moreover, perhaps surprisingly, Makoto Namiki observed that even an unfolding of a tetrahedron can result in an overlap: see Figure 22.1b.

Figure 22.1

(a) Two unfoldings of a prism. (b) A bad unfolding of a tetrahedron.

The conjecture has been verified for certain somewhat narrow classes of polytopes. For example, it holds for so-called prismoids. These are built by taking the convex hull of two polygons that lie in parallel planes, have the same number of sides and the same angles and are positioned in such a way that their corresponding edges are parallel. Another class of polytopes for which the conjecture has been established are the domes. A dome has a base face and all its other faces share an edge with this base.

One approach to the problem is algorithmic. For a proof that all polytopes can be unfolded, we need a good strategy to choose a suitable spanning tree. One could look, for example, for a shortest or a longest spanning tree, which minimizes or maximizes the sum of the lengths of the edges, respectively. Or one can place the polytope in space such that no edge is horizontal and the highest vertex is unique, and then from any other vertex choose the steepest edge or the “rightmost” edge that points upwards. Such rules are motivated by and derived from various “pivot rules” of linear programming, which describe local strategies to move from any given vertex of a polyhedron along edges to the highest vertex. Extensive experiments with such rules were performed by Wolfram Schlickenrieder for his 1997 diploma thesis. None of the strategies tested by him worked for all examples, but for all examples some of his strategies worked.

Further interesting studies motivated by the unfolding conjecture concern relaxations of the problem. For example, there are unfolding techniques that do not cut only along edges, but may cut into faces, such as the source unfolding and the star unfolding discovered by Alexandrov. Here we only sketch the latter technique: For a star unfolding one picks one point on the boundary of the polytope such that it has a unique shortest path to every vertex. The union of these paths form a tree that connects all the vertices. If one cuts the polytope boundary open along this tree, then this is an unfolding that provably has no overlaps.

Almost Disjoint Triangles

How complicated can polyhedral structures be in 3-dimensional space? For example, we are interested in triangulated surfaces on n vertices in ℝ ³, such as the boundary of a tetrahedron, which has n = 4 vertices and n = 6 edges, of an octahedron with n = 6 vertices and e = 12 edges, or of an icosahedron with n = 12 vertices and e = 30 edges.

But what is the maximal number of edges for a triangulated surface in ℝ ³ on n vertices? Certainly it cannot have more than $<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>n</mrow> <mrow>2</mrow> </mfrac> </mfenced>$ edges. This bound is not tight for all n, since for a triangulated surface the number of edges is divisible by 3. Indeed, every triangle is bounded by three edges, while each edge is contained in two triangles, the number e of edges and the number f of triangles satisfy the equation 3f = 2e and thus f is even and e is divisible by three. Another constraint comes from the fact that the surfaces we look at are embedded in ℝ ³. They have an “inside” and an “outside”, so they are orientable, which implies that the Euler characteristic $n - e + f$ is even (it equals 2 − 2g, where g is known as the genus of the surface). Nevertheless, this leads to only slight improvements of the upper bounds. If n is congruent to 0, 3, 4, or 7 modulo 12, then it seems entirely possible that a surface with $e =<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>n</mrow> <mrow>2</mrow> </mfrac> </mfenced>$ exists; its face numbers would be given by $(n,e,f) = (n,<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>n</mrow> <mrow>2</mrow> </mfrac> </mfenced>, \frac{2} {3}<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>n</mrow> <mrow>2</mrow> </mfrac> </mfenced> )$.

Is there such a “neighborly” triangulated surface for all these parameters? For small values of n it seems so: For n = 4 we have the tetrahedron, and for n = 7 there is a triangulated surface, known as the Császár torus, which consists of 14 triangles and $<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>7</mrow> <mrow>2</mrow> </mfrac> </mfenced> = 21$ edges. At the next n where we get integer parameters, n = 12 and e = 66 and g = 6, it is known that combinatorial schemes for suitable triangulated surfaces exist; indeed, this was established for all n ≡ 0, 3, 4, or 7\kern 18mu ({\rm mod}\kern 6mu 12) as part of the so-called Map Color Theorem by Ringel et al. (1974). However, none of the 59 combinatorial schemes for such a surface can be realized as a triangulated surface in ℝ ³. This was established by Jürgen Bokowski, Antonio Guedes de Oliveira, and finally Lars Schewe quite recently.

But let us get beyond the small parameters. What can we expect when n gets large? Will the maximal number of edges in a triangulated surface with n vertices grow quadratically with n, or much slower? All we know at the moment is that the maximal e grows at least as fast as nlogn; this can be seen from surfaces that were constructed by Peter McMullen, Christoph Schulz, and Jörg Wills in 1983.

However, Gil Kalai has proposed studying a closely-related problem that is even easier to state, and may be similarly fundamental:

Given n points in 3-dimensional space, how many triangles could they span that are disjoint, except that they are allowed to share vertices?

So for Kalai’s problem the triangles are not allowed to share an edge, and they are not allowed to intersect in any other way (see Figure 22.2). Let us call this almost disjoint triangles.

Figure 22.2

Almost disjoint triangles spanned by 7 points.

Without loss of generality we may assume that the n points that we use as vertices lie in a general position, no three of them on a line and no four of them in a plane. Clearly the maximal number T(n) of vertex disjoint triangles on n points is not larger than $\frac{1} {3}<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>n</mrow> <mrow>2</mrow> </mfrac> </mfenced>$. But is

$$T(n)\ \leq \ \frac{1} {3}<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>n</mrow> <mrow>2</mrow> </mfrac> </mfenced>$$

a tight upper bound for infinitely many values of n? Does T(n) grow quadratically when n gets large? All we know is that there is a lower bound that grows like n ^3 ∕ 2: Gyula Károlyi and Jozsef Solymosi in 2002 presented a very simple and elegant method to position $n = {m}^{2} +<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>m</mrow> <mrow>2</mrow> </mfrac> </mfenced>$ points in ℝ ³ that span $m<mfenced-6 separators="" open="(" close=")"> <mfrac-1 linethickness="0"> <mrow>m</mrow> <mrow>2</mrow> </mfrac> </mfenced>$ almost-disjoint triangles.

Representing Polytopes with Small Coordinates

A famous theorem by Steinitz from 1922 characterizes the graphs of 3-dimensional convex polytopes. It states:

Theorem 22.1.

A finite graph G is the edge graph of a polytope P if and only if G is planar and 3-connected.

Obtaining a polytope from a given such graph is a construction problem. Here one is especially interested in nice realizations. Of course, the meaning of “nice” depends on the context. One possibility is to ask for a polytope that has all its edges tangent to a sphere. Such a realization exists and it is essentially unique. This can be derived from the Koebe–Andreev–Thurston circle packing theorem. However, the edge tangent realizations are not combinatorial, and in general they have irrational vertex coordinates. One can also ask for rational realizations, such that all vertex coordinates are rational, or equivalently (after multiplication with a common denominator) for integral realizations. The existence of such realizations can be derived from Steinitz’ original proofs. Just how large would the integers have to be?

Figure 22.3 shows a dodecahedron realized with very small integer coordinates due to Francisco Santos.

Figure 22.3

Small coordinates for the dodecahedron.

The big open problem is:

Can every 3-dimensional convex polytope with n vertices be realized with its vertex coordinates in the integer grid $\{0,1,\ldots,f{(n)\}}^{3}$, where f is a polynomial?

All we know at the moment are exponential upper bounds on f(n). The first such bounds were derived by Shmuel Onn and Bernd Sturmfels in 1994; they were subsequently improved to f(n) < 148ⁿ. But indeed we know of no lower bounds that would exclude that all combinatorial types can be realized with f(n) < n ². A recent result by Erik Demaine and André Schulz from 2010 is that for the very special case of stacked polytopes (that is, obtained from a tetrahedron by repeatedly stacking a flat pyramid onto a facet), realizations with polynomially-bounded integer coordinates exist. But do these exist for all graphs of 3-polytopes?

Polyhedra that Tile Space

An innocent-sounding question is

Which convex polytopes can be used to tile 3-dimensional space?

Unfortunately, answering this question seems to be quite difficult. Indeed, not even the 2-dimensional version of this problem has been solved completely, although this has been claimed and believed several times, starting with a paper by Karl Reinhardt from 1918. Nevertheless, for tilings of the plane it is not hard to see that any convex polygon that admits a tiling of the plane—that is, such that the plane can be completely covered by congruent copies of this polygon, without gaps and without overlapping interiors—can have at most six sides. The reason for this is topological and can be connected to Euler’s polyhedron formula. Clearly the regular hexagon can be used to tile the plane (any bee knows that), but many other types of convex hexagons admit such a tiling as well.

One dimension higher, we all know the tiling of space by congruent cubes, which have 8 faces. However, it is also not hard to see that translates of the so-called permutahedron with its 14 faces and 24 vertices tile space face-to-face. So this begs the question:

What is the maximal number of faces for a convex polytope that allows for a tiling of 3-space by congruent copies?

In 1980, the crystallographer Peter Engel produced four types of polytopes with 38 faces that tile space, and up to now this record apparently has not been topped. On the other hand, no finite upper bound is known, and the answer may as well be that there is no finite upper bound. The problem seems to be that the only effective method to produce such tilings is to look at dot-patterns (discrete point sets) in ℝ ³ that have a transitive symmetry group, that is, such that for any two points in the pattern there is a symmetry of space that moves one point to any other one. For such a point configuration S ⊂ ℝ ³ all the Voronoi domains

$$V _{s} :=\{ x \in {\mathbb{R}}^{3} :\| x - s\|\,\leq \,\|x - sprime\|\,\text{for all}\,sprime \in S\}$$

for s ∈ S are congruent. The Voronoi domain of s collects all points in space for which no other point in S is closer. Figure 22.4 shows an excerpt of a symmetric dot pattern with its Voronoi cells.

Figure 22.4

A tiling by congruent pentagons generated by the Voronoi construction applied to a symmetric dot pattern.

The Voronoi construction applied to symmetric dot patterns is very effective in producing tilings by congruent polytopes. Indeed, Engel’s four examples with 38 faces were produced this way. However, it is also known that for tilings of this type the number of faces is bounded.

So symmetry helps to construct tilings. We should, however, not rely on this too much. In his famous list of 23 problems from the 1900 International Congress of Mathematicians in Paris, David Hilbert had asked as part of his 18th problem whether there could be a convex polytope that tiles 3-dimensional space, but such that there is no tiling that would have a symmetry group that moves tiles to tiles. The answer has long been known to be yes: such tilings exist. For example, various types of quasicrystals (Nobel Prize in Chemistry 2011!) demonstrate this. This shows that even though symmetry helps a lot in constructing tilings, it should not be used as our only resource.

Fatness

Whereas regular convex polytopes (the Platonic solids) have been studied since antiquity, general convex polytopes came into the focus of attention much later. To Descartes and Euler we owe the “Euler polyhedron formula.” In modern notation, where we write f _i for the number of i-dimensional faces of a convex polytope, it states that every 3-dimensional convex polytope satisfies

$$f_{0} - f_{1} + f_{2}\ =\ 2.$$

In 1906 Ernst Steinitz characterized the set ℱ ₃ of all possible triples (f ₀, f ₁, f ₂) for convex polytopes:

$$\begin{array}{rlrlrl} \mathcal{F}_{3} & =\{ (f_{0},f_{1},f_{2}) \in {\mathbb{R}}^{3} : f_{ 0} - f_{1} + f_{2}\ =\ 2, & & \\ &\qquad f_{2} \leq 2f_{0} - 4,f_{0} \leq 2f_{2} - 4\}. & & \end{array}$$

More than one hundred years later, no similarly complete description is available for the possible sequences of face numbers, or f-vectors, of d-dimensional polytopes for any d > 3. Indeed, we know that the f-vectors of d-dimensional convex polytopes satisfy essentially only one linear equation, the so-called Euler–Poincaré equation:

$$f_{0} - f_{1} + f_{2} -\ \cdots \ + {(-1)}^{d-1}f_{ d-1}\ =\ 1 - {(-1)}^{d}.$$

However, we do not know all the linear inequalities. In particular, we would be interested in linear inequalities that hold with equality for the d-dimensional simplex, which has $f_{i} = \binom{d + 1}{i + 1}$, as these special inequalities describe the “cone of f-vectors.”

To make this concrete, let us concentrate on the case d = 4. Here everything boils down to the question whether the parameter called fatness,

$$\Phi \ :=\ \frac{f_{1} + f_{2} - 20} {f_{0} + f_{3} - 10},$$

can be arbitrarily large for 4-polytopes. Can it be, say, larger than 10? Or is it true that

$$f_{1} + f_{2} - 20\ \leq \ 10(f_{0} + f_{3} - 10)$$

for all convex 4-dimensional polytopes? This parameter is called “fatness” because it measures how “fat” an f-vector (f ₀, f ₁, f ₂, f ₃) is in the middle, i.e., how big the sum of the entries f ₁ and f ₂ is in comparison to the sum of f ₀ and f ₃.

Indeed, it is not hard to show that the fatness parameter Φ ranges between 2. 5 and 3 for simple and simplicial polytopes. However, it is Φ = 4. 52 for a fascinating 4-dimensional regular polytope known as the “24-cell,” which has f ₀ = 24 vertices and f ₃ = 24 facets, which are regular octahedra; its complete f-vector is (f ₀, f ₁, f ₂, f ₃) = (24, 96, 96, 24). An even higher value of Φ = 5. 021 is achieved for the “dipyramidal 720-cell” constructed in 1994 by Gabor Gévay, which has f-vector (720, 3600, 3600, 720). Finally, a class of polytopes named “projected deformed products of polygons,” constructed by the second author in 2004, get arbitrarily close to Φ = 9. That’s where we stand at the time of writing. But is there a finite upper bound at all?

This may read like a problem of 4-dimensional geometry and thus outside our range of visualization, but it isn’t really, since the boundary of a 4-dimensional polytope is of dimension 3. Thus one can relate the question to problems about polytopal tilings in 3-space. Here is one such problem:

Are there normal face-to-face tilings of 3-space by convex polytopes in which

• (1) all tiles have many vertices, and

• (2) each vertex is in many tiles?

For example, in the usual tiling of space by unit cubes all tiles have 8 vertices and each vertex is in 8 tiles. For a normal tiling we require that there be a lower bound for the inradius and an upper bound for the circumradius of the tiles. This is satisfied, for example, if there are only finitely many types of tiles. It is not too hard to show that either of the two conditions (1) and (2) can be satisfied. But can they be satisfied by the same tiling, at the same time? If no, then fatness Φ for 4-polytopes is bounded.

The Hirsch Conjecture

One of the biggest mysteries in convex geometry is about the graphs of convex polytopes and their diameters. The graph of a polytope is a combinatorial model which captures vertex-edge incidences. Such a graph has the vertices of the polytope as nodes and two nodes are adjacent in the graph if they are connected by an edge as vertices in the polytope. Figure 22.5 shows the octahedron and its graph.

Figure 22.5

A polytope and its graph.

The diameter of a graph is the greatest distance of two vertices in the graph, where the distance of two vertices is the length of the shortest path connecting them. In 1957 Warren Hirsch raised the question:

What is the maximal diameter of the graph of a d-polytope with n facets?

He conjectured that

$$\Delta (d,n) \leq n - d,$$

where Δ(d, n) denotes the above maximal diameter. Even though decades of research went into a solution of this problem, for over 50 years little progress was made. Finally, in May 2010, Francisco Santos announced a counterexample. By an explicit construction he could demonstrate that Δ(43, 86) > 43.

While this certainly was a breakthrough, it is merely a first step in answering the above question. Santos’ construction does not even rule out an upper bound on the diameter that is linear in n − d. Many researchers in discrete geometry believe that the real question is whether there is a polynomial bound in n and d. The best upper bound for general d-polytopes was derived by Gil Kalai and Daniel Kleitman in 1992. By using a strictly combinatorial approach they were able to prove that

$$\Delta (d,n)\ \leq \ {n}^{2+\log _{2}d},$$

but of course this is still very far from a polynomial bound. Furthermore, by a result of Larman it follows that if one fixes the dimension d, then there is a bound that is linear in n. In general it is sufficient to prove an upper bound for simple polytopes: The facets of a non-simple polytope can be perturbed such that one gets a simple polytope. This new polytope has a graph whose diameter is at least as large as for the original graph.

Besides its importance for polyhedral geometry, the question also relates closely to linear programming. The maximal graph diameter Δ(d, n) is a lower bound for the number of steps that the simplex algorithm would need on a problem with n constraints in d variables for any pivot rule that would select the edges. Thus researchers from Operations Research and Mathematical Optimization are interested in the Hirsch Conjecture as well.

Unimodality

In 1970 McMullen settled the long-standing open question, “What is the maximal number of k-faces of a d-polytope on n vertices?” He confirmed that neighborly simplicial polytopes are extremal with regard to their f-vectors: A neighborly polytope is a polytope such that every subset of the vertices of cardinality at most ⌊d ∕ 2⌋ is the vertex set of a face. One well-known class of such polytopes is the cyclic polytopes. These can be defined as the convex hull of finitely many points on the moment curve

$$\alpha : \mathbb{R}\rightarrow {\mathbb{R}}^{d},\quad t\longmapsto (t,{t}^{2},\ldots,{t}^{d}).$$

That is, one chooses n different reals, $t_{1} < \cdots < t_{n}$, and calls

$$C_{d}(n) = \text{conv}(\alpha (t_{1}),\ldots,\alpha (t_{n}))$$

the d-dimensional cyclic polytope on n vertices. (A simple analysis, using the Vandermonde determinant, shows that cyclic polytopes are simplicial, and that the combinatorial type does not depend on the particular parameters t _i chosen.) Figure 22.6 shows a realization of C ₃(6).

Figure 22.6

Construction of a cyclic 3-polytope with 6 vertices.

Despite McMullen’s Upper Bound Theorem, there are other questions about the face numbers of polytopes, also closely connected to the cyclic polytopes, which are not well understood, yet — the most tantalizing ones connected to unimodality. A sequence of numbers is called unimodal if it first increases and then decreases with no “dips” in-between. It was proved only recently, by László Major, that the f-vectors of all cyclic polytopes are unimodal. (This was a long-standing open problem despite the fact that we have explicit formulas for the f-vectors of cyclic polytopes.) However, in 1981 Björner was able to construct polytopes with non-unimodal f-vectors by cleverly modifying a cyclic polytope of dimension at least 20.

This was quite a surprise as already in the late 1950s Theodore Motzkin had conjectured that allf-vectors of convex polytopes are unimodal. (Later, in 1972, Dominic Welsh came up with the same conjecture again.) Unfortunately, it is not quite that easy. At a conference in Graz, Austria, in 1964 Ludwig Danzer presented a first construction for very high-dimensional polytopes with non-unimodal f-vector. Later Jürgen Eckhoff came up with another construction that is ingeniously easy, and gets us down to dimension 8. Indeed, here is a sketch for his construction. For this we again start with a cyclic polytope, C ₈(25), which is a simplicial polytope on 25 vertices and 7125 facets, with f-vector

$$\begin{array}{rlrlrl} &(25,300,2300,12650,33750,44500, & & \\ &\quad 28500,7125). & & \end{array}$$

Its dual polytope C ₈(25)^∗ is a simple polytope that has 7125 vertices and 25 facets. Now one can cut off one of the simple vertices of the dual polytope, which yields a simplex facet. One can then “glue” these two polytopes along one of the facets of C ₈(25) and the simplex facet of the modified C ₈(25)^∗. The resulting polytope, called a “connected sum” and denoted by C ₈(25)#C ₈(25)^∗, has the f-vector

$$\begin{array}{rlrlrl} &(7149,28800,46800,46400,46400,46800, & & \\ &\quad 28800,7149) & & \end{array}$$

with a small but noticable dip in the middle — it is not unimodal!

So far no one succeeded in constructing a polytope with non-unimodal f-vector of dimension less then 8. It is only known that all f-vectors of polytopes up to dimension 5 are unimodal. Furthermore, all known examples of polytopes with non-unimodal f-vector have lots of vertices; the current record is 1320 vertices. All this begs the questions:

Are there “small” polytopes that have non-unimodal f-vectors?That is, are there polytopes of dimension smaller than 8?And are there such polytopes with much fewer than, say, 1000 vertices?

One can also speculate how large the “dips” in f-vectors polytopes can be. Are they always tiny? Indeed, Imre Bárány asked the following intriguing question, which tries to exclude dramatically deep dips:

Is it true that the smallest face number of a polytope is always given by the number of vertices, or the number of vertices (or both)? That is, do we always have

$$f_{i}(P) \geq \min \{ f_{0}(P),f_{d-1}(P)\}$$

for the face numbers of a d-dimensional polytope P?

We don’t know. And indeed currently no-one seems to be able to even prove that

$$f_{i}(P) \geq \frac{1} {1000}\min \{f_{0}(P),f_{d-1}(P)\}$$

holds in general, for all d-polytopes P and 0 < i < d − 1. The unimodality questions, and in particular Bárány’s problem, demonstrate strikingly how little we know about the face numbers of polytopes.

Decompositions of the Cube

Consider the d-dimensional cube I _d  = [0, 1]^d and define the following parameters:

• Let C(I _d ) be the minimal number of d-dimensional simplices needed for a cover of I _d . A cover of I _d is a collection of simplices such that the union of all simplices is I _d . The interiors of simplices are allowed to intersect.

• If all vertices of a cover are also vertices of I _d , we speak of a vertex cover. The minimal cardinality of a vertex cover will be denoted by C ^v(I _d ).

• The minimal number of dissections of I _d will be abbreviated by D(I _d ). A dissection is a decomposition of I _d into d-dimensional simplices whose interiors are pairwise disjoint but that do not necessarily intersect in a common face. So simplices are allowed to touch but the interiors must not intersect.

• D ^v(I _d ) is the same as D(I _d ), except that we again require the vertices of the simplices to be vertices of I _d —such a dissection is called a vertex dissection.

• We define T(I _d ) to be the size of the minimal triangulation of I _d , where triangulation means decomposition of I _d into pairwise disjoint d-simplices which intersect in a common face or not at all.

• Finally, T ^v(I _d ) is defined analogously to D ^v(I _d ).

Three obvious questions are:

• 1. Given the dimension, what are the values for the parameters above?

• 2. Can we give good estimates of the parameters for large d?

• 3. And what is their relationship among each other?

For the rest of this description we will write C instead of C(I _d ), etc. With regard to the last question, we can easily sum up what is currently known:

$$C\, \leq \, {C}^{v},D\, \leq \, T,{D}^{v}\, \leq \, {T}^{v}.$$

The only non-trivial relation is C ^v ≤ T, but this follows from a result by Bliss and Su. The status of the first two questions cannot be summarized so concisely. Best studied seems to be the parameter T ^v. The case d = 2 is straightforward but already d = 3 allows vertex triangulations of different cardinality, as demonstrated by Figure 22.7.

Figure 22.7

Two triangulations of a 3-cube.

To get an upper bound on T ^v one considers the so-called standard triangulation. It is of size d! and one constructs it by linking a simplex to each permutation π ∈ S _d by using the following description

$$\begin{array}{rlrlrl} \Delta _{\pi } & =\{ (x_{1},\ldots,x_{d}) \in {\mathbb{R}}^{d} : & & \\ &{4.0pt} \quad 0 \leq x_{\pi (1)} \leq \cdots \leq x_{\pi (d)} \leq 1\}. & & \end{array}$$

This triangulation is maximal among those that only use vertices of the cube, but minimal only for d = 2. For lower bounds one directly looks at the more general case of C ^v. To get asymptotic estimates for example, the following idea is applied: If V (d) denotes the maximal determinant of a 0 ∕ 1-matrix, then V (d) ∕ d! is an upper bound of the volume of the largest simplex in I _d and we get

$${C}^{v} \geq \frac{d!} {V (d)}.$$

Determining V (d) is not easy but one can use the Hadamard inequality to bound it. By using hyperbolic volume instead of Euclidean volume, Smith obtained in 2000 the bound

$${C}^{v},D,T,{D}^{v},{T}^{v} \geq \frac{{6}^{d/2}d!} {2{(d + 1)}^{(d+1)/2}}.$$

Glazyrin recently improved this bound for T ^v:

$${T}^{v} \geq \frac{d!} {{(\sqrt{d}/2)}^{d}}.$$

The following table sums up lower bounds which are results of several research articles. Bold entries denote optimal bounds.

The Ball-and-Cube Problem

Consider the d-dimensional ball

$$B_{d} =\{ x \in {\mathbb{R}}^{d} :\| x\| \leq 1\}$$

and let P _d  ⊆ ℝ ^d be a convex polytope of dimension d with 2d facets that contains B _d . One example of such a polytope is the d-dimensional unit cube

$$\begin{array}{rlrlrl} C_{d} & =\{ (x_{1},\ldots,x_{d}) \in {\mathbb{R}}^{d} : & & \\ &{16.0pt} \vert x_{i}\vert \leq 1\,\text{for}\quad i = 1,\ldots,d\}. & & \end{array}$$

Furthermore, for such a polytope P _d let σ(P _d ) be the maximal distance between some point of P _d and the origin 0 ∈ ℝ ^d. Then a conjecture of Chuanming Zong (who also suggested that we include this problem), states that

$$\sigma (P_{d}) \geq \sqrt{d},$$

where equality is supposed to hold if and only if P _d is congruent to C _d . It is not difficult to verify this conjecture for d = 2: Assume that it is not correct, i.e., there exists a quadrilateral P ₂ that contains the unit disc but has $\sigma (P_{2}) < \sqrt{2}$. Using the center of the disc as a vertex, one can dissect it into four triangles whose vertices are the corners of the quadrilateral and the origin. Our assumption in particular means that the edge length of an origin-corner edge is strictly less than $\sqrt{2}$. (Compare Figure 22.8)

Table 1

Figure 22.8

Solution of the ball-and-cube problem for dimension 2.

Since the function arccos​​ : [ − 1, 1] → [0, π] is strictly monotonically decreasing, we have for the angle α in the drawing

$$\cos \alpha > \frac{1} {\sqrt{2}}\quad \Longrightarrow\quad \alpha <\arccos \frac{1} {\sqrt{2}} = \frac{\pi } {4}.$$

In total we have an angle sum of strictly less than $8 \cdot \frac{\pi } {4} = 2\pi$ for a whole tour around the origin—clearly a contradiction. Besides this easy case not much is known. László Fejes Toth was able to prove an equivalent conjecture for d = 3 and Dalla et al. verified the statement for d = 4. All higher-dimensional cases are still open at the time of writing (2011).

The 3^d Conjecture

The last century there has been amazing progress in the understanding of face numbers of convex polytopes. As discussed in Problem 5 (Fatness), the case d = 3 was solved by Steinitz in 1906: The possible f-vectors are

$$\begin{array}{rlrlrl} \{(f_{0},f_{1},f_{2}) & \in {\mathbb{Z}}^{3} : f_{ 0} - f_{1} + f_{2} = 2, & & \\ f_{2} & \leq 2f_{0} - 4,\ f_{0} \leq 2f_{2} - 4\}. & & \end{array}$$

The first condition is Euler’s equation, the first inequality is satisfied by equality for polytopes where all faces are triangles, while the second inequality characterizes polytopes where all vertices have degree 3 as the extreme case. In the case d = 4 one basic problem that remains is the fatness problem discussed above. A complete answer for d-dimensional simple or simplicial polytopes is available via the so-called g-Theorem proved by Billera–Lee and Stanley in 1980.

In contrast to this, it is amazing how little we know about centrally-symmetric convex polytopes, that is, polytopes that are left unchanged by a reflection in the origin in ℝ ^d. Let’s first look at the 3-dimensional case again. Here the possible f-vectors can be described as

$$\begin{array}{rlrlrl} &\{(f_{0},f_{1},f_{2}) \in {(2\mathbb{Z})}^{3} : f_{ 0} - f_{1} + f_{2} = 2, & & \\ &\quad f_{2} \leq 2f_{0} - 4,f_{0} \leq 2f_{2} - 4,\ f_{0} + f_{2} \geq 14\}. & & \end{array}$$

All the face numbers of a centrally-symmetric polytope are even, thus we have (f ₀, f ₁, f ₂) ∈ (2ℤ)³. We recognize Euler’s equation and the two inequalities from above. And then there is an additional relation, which for d = 3 is easy to prove: A centrally-symmetric 3-polytope has at least 6 vertices, and if it has only 6 vertices, then it must be an octahedron which has 8 facets. If, however, the centrally-symmetric 3-polytope has at least 8 vertices, then it also has at least 6 facets with the only extreme case of an affine cube. In summary, this yields the third inequality, which by Euler’s equation we can rewrite as

$$f_{0} + f_{1} + f_{2} + f_{3} \geq 27,$$

with equality if and only if the polytope is either a cube or an octahedron. In 1989 Gil Kalai asked whether a similar statement was true in all dimensions:

Does every d-dimensional centrally-symmetric polytope have at least 3^d non-empty faces?

Kalai’s question fits into a series of three basic conjectures:

The 3^d conjecture:

(Kalai 1989)Every centrally-symmetric d-dimensional polytope satisfies $f_{0} + f_{1} + \cdots + f_{d} \geq {3}^{d}$.

The flag conjecture:

(Kalai 2008)Every centrally-symmetric d-dimensional polytope satisfies $f_{0,1,2,\ldots,d-1} \geq {2}^{d}d!$.

The Mahler conjecture:

(Mahler 1939)Every centrally-symmetric convex body K satisfies Vol(K) ⋅Vol(K ^∗) ≥ 4^d ∕ d! , where K ^∗ is the polar of K.

These three conjectures are remarkable since they seem basic; they have been around for quite a while, but we know so little about them. The 3^d conjecture was proved for d ≤ 4 by Sanyal et al. in 2009, but is open beyond this. The flag conjecture is not even known for d = 4. Yet worse, the Mahler conjecture has been an object of quite some scrutiny, but it seems open even for d = 3.

The three conjectures belong together since we believe we know the answer—the same answer for all of them. Indeed, the class of Hanner polytopes introduced by Olof Hanner in 1956 is obtained by starting with a single centrally-symmetric interval such as [ − 1, 1] ⊂ ℝ and then taking products and polars—or equivalent, taking products and direct sums of polytopes. It is easy to compute that all d-dimensional Hanner polytopes have exactly 3^d non-empty faces, they have exactly 2^d d! complete flags of faces, and they have exactly Mahler Volume $\mathrm{Vol}(P) \cdot \mathrm{Vol}({P}^{{\ast}}) = {4}^{d}/d!$. But are they the only centrally-symmetric polytopes with these properties? And can’t there be any other polytopes with even smaller values? This is not known.