Open problem session of HUJI-COMBSEM: Problem #5, Gil Kalai – the 3ᵈ problem

This post continues to describe problems presented at our open problems session back in November 2020. Here is the first post in the series.  Today’s problem was presented by me, and it was an old 1989 conjecture of mine.

A convex set K is centrally symmetric if x \in K implies that -x \in K.

Conjecture: Let P be a centrally symmetric d-polytope. Then P has at least 3ᵈ non-empty faces.

Here we count P itself as a face.

Before we continue let me mention a winter school on “The Interplay between High-Dimensional Geometry and Probability”, January 11-15. Among other exciting lectures Bo’az Klartag will give 3 lectures on Yuansi Chen’s work on the KLS conjecture, that we discussed in this post.

Now back to the 3ᵈ conjecture. A case of equality is the d-dimensional cube C_d. The faces of C_d corresponds to (-1,1,*)-vectors of length d. Given such a vector it corresponds to a face of the cube whose vertices are obtained by replacing the *’s with ±1 in all possible ways.  Of course the dual of C_d also has 3^d non-empty faces.

 

Schlegel diagram of the octahedral prism, a 4-dimensional Hanner polytope.  (attribution: Robert Webb’s Stella software as the creator of this image along with a link to the website: http://www.software3d.com/Stella.php. via Wikipedea.)

Some comments

Here are some points raised in the discussion and further comments.

  1. There are many cases of equality – all Hanner polytopes. Those are obtained from intervals by taking the two operations, a) Cartesian product, b) moving from a polytope P to its polar-dual P*, and apply them in all possible ways.
  2. Nati asked if a (2+\epsilon)^d lower bound is known. To the best of my knowledge even this is not known.
  3. Gideon asked about the connections with Mahler’s conjecture that for every d-dimentional centrally symmetric body K, vol(K)vol(K*) \ge 4^n/n!  . Indeed the cases of equality are conjectured to be the same – the class of Hanner polytopes. (Mahler’s conjecture and its relations to combinatorics would deserve a separate post.) The recent paper Flag numbers and floating bodies by F Besau, C Schütt, EM Werner looks very relevant.
  4. For simplicial polytopes the conjecture follows from results of Stanley (1986) and is related t0 a result by Barany and Lovasz (1982).
  5. The conjecture is related to a 1979 theorem of Figiel, Lindenstrauss, and Milman that asserts that for every centrally symmetric d polytope \log f_0(P) \log f_{d-1}(P) \ge \gamma d, for some universal constant \gamma.
  6. A somewhat more general conjecture would be that the number of k-faces of the barycentric subdivision of K is always as large as the number of k-faces of the barycentric subdivision of C_d. The case k=0 is the original conjecture and I regard the case k=d-1 (sometimes referred to as the “flag-number conjecture”) as even closer to Mahler’s conjecture. See the paper by Schmidt and Ziegler, Ten Problems in Geometry.
  7. In this paper by Raman Sanyal, Axel Werner, and Günter M. Ziegler, the conjecture is proved for d \le 4. The proof is rather involved and rely on an extension of the lower bound theorem. (It does not extend to polyhedral spheres.)  The paper also gives counterexamples for two much stronger conjectures that I made in my 1989 paper.

Some further comments

  1. Hanner polytopes form an exciting family of polytopes. They have the maximum Banach-Mazur distance from the Euclidean ball, and it is conjectured that only these polytopes attain this maximum. They also have the 2-3 Helly-property (namely every three pairwise intersecting translates have a point in common. It was proved by Lima and Jensen that this property holds only by Hanner polytopes!
  2. The proof for the conjecture for d=4 involves the “extended lower bound inequality”.
  3. Another conjecture of mine of a similar spirit is: a polyhedral d-manifold (more generally, a regular CW manifold) in dimension d which is not a sphere has at least 2^{(3d+4)/2} faces. (Including the empty face.)
  4. Flag (d-1)-dimensional spheres also have at least 3^d faces. This follows from a theorem by Roy Meshulam.
  5. Completely balanced (d-1)-dimensional spheres also have at least 3^d faces. (I think.) (What about zonotopes, you may ask.)
  6. The class of spheres in items 4 and 5 are simplicial. So an extensions of these classes to classes of polyhedral spheres (and regular CW spheres) would be interesting.
  7. d-Polytopes with no triangular 2-faces also have at least 3^d non-empty faces this follows from a theorem of Blind and Blind.
  8. Looking around in papers that referred to my old paper I discovered the following appealing class of polytopes and interesting conjecture about them. A polytope P is 2-level if for every facet F of P there is a hyperplane parallel to the hyperplane through F that contains all vertices not in F. The conjecture is that for such a d-polytope P, f_0(P)f_{d-1}(P)\le d2^{d+1}. This conjecture was made in the paper Enumeration of 2-level polytopes by  Bohn,  Faenza,  Fiorini,  Fisikopoulos, Macchia, and Pashkovich. (Update: Giulia commented that the conjecture on 2-level polytopes by Bohn et al. was recently solved by Andrey Kupavskii and Stefan Weltge: https://arxiv.org/abs/2008.07153.)
  9. Interesting classes of polytopes arising from graphs that are very near the conjecture can be found in the paper Face numbers of centrally symmetric polytopes from split graphs by Freij, Henze, Schmitt, and Ziegler. See also Independence complexes of perfect graphs by Freij and Henze in this report.

Update (Jan 12,2021): Looking at old correspondence with Ragnar Freij, Matthias Henze, and Günter Ziegler, I came across the following conjecture that related the flag number conjecture and Mahler’s conjecture. Let P be a centrally symmetric d-polytope. Let 1+m(P)=vol(K)/vol(K*)/ (4^d/d!), and let 1+fn(P)=mf(P)/(2^dd!). For a centrally symmetric $d$-polytope P, Mahler’s conjecture asserts that m(P) \ge 0 and the flag number conjecture asserts that fn(P) \ge 0.

Conjecture:  fn(P) ≥ 4 m(P)

It is also conjectured that equality holds for Jensen’s polytopes of perfect graphs.

 

 

 

This entry was posted in Combinatorics, Computer Science and Optimization, Geometry, Open problems. Bookmark the permalink.

5 Responses to Open problem session of HUJI-COMBSEM: Problem #5, Gil Kalai – the 3ᵈ problem

  1. Giulia says:

    Dear Gil, I love your conjecture! Let me mention that the conjecture on 2-level polytopes by Bohn et al. was recently solved by Andrey Kupavskii and Stefan Weltge: https://arxiv.org/abs/2008.07153

  2. shacharlovett says:

    Is there a simple proof for a 2^d bound?

    On Sun, Jan 10, 2021 at 7:24 AM Combinatorics and more wrote:

    > Gil Kalai posted: “This post continues to describe problems presented at > our open problems session back in November 2020. Here is the first post in > the series. Today’s problem was presented by me, and it was an old 1989 > conjecture of mine. A convex set K is centrally sy” >

    • Gil Kalai says:

      Dear Shachar, yes, it is easy to show that every d-polytope has at least {d+1}\choose {i+1} i-faces for i=-1,0,1,\dots,d. In fact, you can even easily show by applying induction to the link of a vertex and its antistar that the boundary comlex of every d polytope is a subdivision of the boundary complex of a d-dimensional simplex.

  3. Gil Kalai says:

    Two updates. I added a conjectural relations between the flag number conjecture and Mahler’s conjecture that arose in 2009 discussions with Ragnar Freij, Matthias Henze, and Günter Ziegler. I also think that the 3ᵈ problem could be a nice polymath project and added it to the list here on MO https://mathoverflow.net/a/380964/1532 .

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s