## Five Open Problems Regarding Convex Polytopes

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:

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:

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?