Five Open Problems Regarding Convex Polytopes

About these ads
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.

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

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

  13. Pingback: Vitali Fest « Combinatorics and more

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

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

  16. 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?

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s