The problems

1. The $3^d$ conjecture

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

2. The cube-simplex conjecture

For every k there is f(k) so that every d-polytope with $d \ge f(k)$ 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, $0 \le k \le d-1$,  is it true that $f_k(P) \ge \min (f_0(P),f_{d-1}(P))$?

(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 $(f_1(P)+f_2(P))/(f_0(P)+f_3(P))$ 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 faceof 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 $f_k(P)$ denotes the number of k-faces of P. The f-vector of P is the vector $(f_{-1}(P),f_0(P),f_2(P), \cdots , f_d(P))$. 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 $ \le 1$ for every $x \in P$. 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 $\log f_0(P) \cdot \log f_{d-1}(P) \ge \gamma d$ for some absolute constant $\gamma >0$.  Raman Sanyal, Axel Werner, and Günter Ziegler proved the $3^d$ 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 $3^d$ 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 $d \ge g(d)$ 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

This entry was posted in Combinatorics, Convex polytopes, Convexity, Open problems and tagged , , , . Bookmark the permalink.

19 Responses to Five Open Problems Regarding Convex Polytopes

1. D. Eppstein says:

Welcome 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?

2. Gil Kalai says:

Dear 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 $R^4$. But this is also unknown.

3. Shashi says:

What about Hirsch’s conjecture?

4. Gil Kalai says:

Dear 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 ).

5. D. Eppstein says:

Answering a question from email: the $\Omega(n^{[((d+1)/3)]})$ 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 $R^5$ have the 5-vector $(1,2n,n^2+2n,2n^2+2,n^2+2n,2n,1)$, etc. In general from f-vectors $A[i]$ and $B[i]$ you get a convolved vector $C[i] = \Sigma_{a+b=i}A[a]B[b]$.

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

6. D. Eppstein says:

that 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?

7. Gil Kalai says:

Dear 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 $\bar \Xi e^x$, 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.)

8. D. Eppstein says:

Thanks! 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.

9. Shashi says:

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

10. Gil Kalai says:

David, 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. says:

wait; a polytope is simple, if it is simplicial *and*
its dual is simplicial (only saw the last part, stated explicitly

• Gil Kalai says:

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

11. Pingback: Vitali Fest « Combinatorics and more

12. msdbet says:

I 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?