## The problems

**1. The conjecture**

A centrally symmetric d-polytope has at least non empty faces.

**2. The cube-simplex conjecture**

For every k there is f(k) so that every d-polytope with has a k-dimensional face which is either a simplex or combinatorially isomorphic to a k-dimsnional cube.

**3. Barany’s question**

For every d-dimensional polytope P and every k, , is it true that ?

(In words: the number of k-dimensional faces of P is at least the minimum between the number of vertices of P and the number of facets of P. )

**4.** ** Fat 4-polytopes**

For 4-polytopes P, is the quantity bounded from above by some absolute constant?

**5.** **five-simplicial five-simple polytopes**

Are there 5-simplicial 5-simple 10-polytopes? Or at least 5-simplicial 5-simple d-polytope for some d?

(A polytope P is k-simplicial if all its faces of dimension at most k, are simplices. A polytope P is k-simple if its dual P* is k-simplicial.)

And on a personal note: My beloved, beautiful, and troubled country celebrates 60 today: happy birthday!

Update (May 12): David Eppstein raised in a followup a sort of a dual question to Barany’s. For a d-polytope with n vertices and n facets what is the maximal number of k-faces. For a fixed d and large n the free join of pentagons is conjectured to give asymptotically the best upper bound.

Update (July 29) Gunter Ziegler reminded me of the following additional problem of Barany: Is the number of saturated chains in a d-polytope bounded by some constant (depending on d) times the total number of faces (of all dimensions) of the polytope. A saturated flag is a 0-face inside a 1-face inside a 2-face … inside a (d-1)-face.

## Background

A **convex polytope** is the convex hull of a finite set of points in an Euclidean space. A proper **face**of a polytope P is the intersection of P with a supporting hyperplane. The empty face and P itself are regarded as trivial faces. The convex hull of a set of points which affinely span a d-dimensional space is a d-dimensional polytope or briefly a d-polytope. Faces of polytopes are themselves polytopes, a k-face is a short way to say k-dimensional face. 0-faces are called **vertices**, 1-faces are called **edges **and (d-1)-faces of a d-polytope are called **facets**. The set of faces of a polytope is a POSET (=partially ordered set) which is a “lattice”, “atomic”, and “graded”. For a polytope P denotes the number of k-faces of P. The ** f-vector **of P is the vector . Two d-polytopes P and Q are combinatorially equivalent if there is a bijection between the faces of P and the faces of Q which preserves the order relation.

The simplest d-polytope is the **simplex**: the convex hull of d+1 affinely independent points. The face lattice (=POSET of faces) of a simplex is just the Boolean lattice. A d-polytope is **simplicial **if all its proper faces are simplicies. A polytope is **simple **if its dual is simplicial or, equivalently, if every vertex is included in precisely d edges. A d-polytope is k-simplicial if all its k-faces are simplices. (Here d>k.) The d-cube is the convex hull of all vectors of length d with entries +1/-1.

The five open questions in this post belong to the combinatorial theory of polytopes that deal with the set of faces of polytopes. (There are also interesting metrical and arithmetic questions about polytopes.)

If P is a convex polytope which contains the origin in its interior, the **polar dual **of P is the set of all points y so that for every . There is a 1-1 **order reversing **bijection between the faces of P and the faces of its polar.

A polytope P is **centrally symmetric** if whenever x belongs to P so is -x.

## Remarks:

1. The conjecture was motivated by results by Barany and Lovasz and by Stanley, who gave stronger statements for simplicial centrally symmetric polytopes, and by a theorem of Figiel, Lindenstrauss and Milman that asserts that for arbitrary CS d-polytopes that for some absolute constant . Raman Sanyal, Axel Werner, and Günter Ziegler proved the conjecture for d=4 and refuted some stronger conjectures I had made. All Hanner d-polytopes, namely d-polytopes obtained from [-1,1] by repeating the operations of 1) Cartesian product, 2) taking the polar, have precisely non empty faces.

2. The 120-cell (a 4-polytope whose facets are all dodecahedra) shows that f(2)>4, and I proved that f(2)=5. The conjecture is not known even for simple polytopes. A weaker conjecture asserts that there is a finite list of k-polytopes that for every every d-polytope has a k-face from the list. The fact that g(2)=3 (with the list being :{triangle, quandrangle, pentagon}) follows from Euler’s theorem and perhaps even goes back to Descartes. Kleinschmidt, Meisinger and myself proved g(3)< 10. If we restrict ourselves to simple polytopes then it is true that the analogous g(k) is finite.

3. A positive answer to Barany’s problem would follow from very strong (conjectural) versions of the **upper bound theorem.** This is poor excuse for our inability to answer this question.

4. This is a crucial problem in understanding all linear inequalities among face numbers of 4-polytopes. See, e.g. this paper by Ziegler and this by Eppstein, Kuperberg, and Ziegler.

5. A 4-simple 4-simplicial 8 polytope is known: This is the Gosset polytope.

## More

Much more material on polytopes can be found in Günter Ziegler’s home page and in his papers, book and in the new edition of Grunbaum’s book “Convex polytopes”, which he recently edited with Kaibel and Klee.

Günter Ziegler

D. EppsteinWelcome to the blogosphere! I found this post through Google blog search but, now that I know about it, will check here more regularly.

I posted a followup here. I’m especially curious about the 5-simple 5-simplicial question. Infinitely many 2-simplicial 2-simple polytopes are known (see the EKZ paper and arXiv:math.MG/0304492) but is the same true for 3-simplicial 3-simple?

Gil KalaiDear David, thanks! I am not sure if infinitly many 3-simplicial 3-simple d-polytopes are known for d=6 or some other fixed d. It was also conjectured that 2-simplicial 2-simple 4-polytopes are dense in the space of all convex body in . But this is also unknown.

ShashiWhat about Hirsch’s conjecture?

Gil KalaiDear Shashi, the Hirsch’s conjecture deseves a special post; unfortunately not much progress was made for a long time.

Just a little preview – The Hirsch Conjecture asserts that the diameter of a graph of a d-polytope with n facets is at most n-d. It is not even known if there is a polynomial upper bound (in n and d ).

D. EppsteinAnswering a question from email: the construction for the number of intermediate faces of a d-polytope with O(n) vertices and facets is to embed a collection of n-gons on mutually skew 2-planes and take their convex hull. The resulting polytope has an f-vector that’s the convolution of the f-vectors of the polygons. Thus, one polygon in two dimensions has the f-vector (1,n,n,1); two of them on skew planes in have the 5-vector , etc. In general from f-vectors and you get a convolved vector .

I made this observation in an email to Jeff Erickson and Nina Amenta in July 1997, but I think the only place it has been publically described is Jeff’s web page http://compgeom.cs.uiuc.edu/~jeffe/open/intricate.html

D. Eppsteinthat should be n^{floor((d+1)/3)} and Σ_{a+b=i} A[a]B[b]. I guess wordpress strips out sub and sup html markup in comments?

Gil KalaiDear David,

I tried to edit your comment. To write latex here one has to do

dollarsign latex formula dollarsign

A common mistake for me is to write say $\latex \bar \Xi e^x$ this will not work because of the \ before latex, now I will delete it and try again , voila!!

Regarding polytopes, you raised the problem “what is the maximum number of k-faces for a d-polytope with n vertices and n facets.” It is quite interesting! (Barany’s question ask for the minimum number.)

D. EppsteinThanks! By the way, where did you get the photo of Günter? Under what conditions is it usable? I like it better than the boring snapshot that’s on his Wikipedia article now.

ShashiThanks for your reply – I am looking forward to your post on Hirsch’s conjecture.

Gil KalaiPost authorDavid, Gunter is “in charge” of 2008- mathematics year in Germany and you can find many photos, interviews, and even video clips on his homepage.

Brian H.wait; a polytope is simple, if it is simplicial *and*

its dual is simplicial (only saw the last part, stated explicitly

Gil KalaiPost authorNo no, A polytope is simple if its dual is simplicial. (Only the simplex is both simple and simplicial.)

Pingback: Walking Randomly » Carnival of Mathematics #33 - The rushed edition!

Pingback: Telling a Simple Polytope From its Graph « Combinatorics and more

Pingback: Vitali Fest « Combinatorics and more

Pingback: An Extremal Property of the 600-Cell, Poincaré Dodecahedral Sphere, Polytopes with Icosahedral Faces, and CAT People | Combinatorics and more

Pingback: Updates, Boolean Functions Conference, and a Surprising Application to Polytope Theory | Combinatorics and more

msdbetI have a linear programming problem where the polytope is described as a convex hull of an exponential number ($2^d$) of points in d-dimensional space. What could be an approach? Do you first identify the set of vertices from the $2^d$ points and check which vertex maximizes the objective? Is there an efficient algorithm to identify the set of vertices from the given set of $2^d$ points?

Pingback: Some old and new problems in combinatorics and geometry | Combinatorics and more