Category Archives: Convex polytopes

Tokyo, Kyoto, and Nagoya


Near Nagoya: Firework festival; Kyoto: with Gunter Ziegler; with Takayuki Hibi, Hibi, Marge Bayer, Curtis Green and Richard Stanly; Tokyo: Peter Frankl; crowded crossing. Added later: Mazi and I at the same restaurant taken by Stanley.

I just returned from a trip to Japan to the FPSAC 2012 at Nagoya and a workshop on convex polytopes in Kyoto. As in my first visit to Osaka in 1999 I found Japan stunning, and this time I was able to share the experience with my wife.

Kyoto: The week before FPSAC there was a workshop at RIMS devoted to convex polytopes. Some highlights: A classical result by Venkov and McMullen characterizes polytopes whose translates tile the Euclidean d-space.  Sinai Robins talked about his work with Nick Gravin and Dima Shiryaev about k-tilings (every point is covered k times).  Not a full characterization yet but already some impressive results. Gunter Ziegler talked about his work with Karim Adiprasito disproving an old conjecture by Shephard which asserts that there are only finitely many projectively unique d-polytopes for every dimension d. This is false above dimension 81.  Eran Nevo talked about his solution with Satoshi Murai of the generalized lower bound conjecture and some subsequent works on triangulated manifolds. There were several talks relating Ehrhard polynomials of polytopes with enumerative combinatorics,  and several talks on algebraic geometry, toric varieties, Fano varieties, and mirror symmetry. Here are the slides of my lecture entitled open problems on convex polytopes I’d love to see solved (but some further explanations for some parts are needed). I hope to return to some of the topics of the workshop in a later post.

Nagoya: FPSAC (Formal power series and algebraic combinatorics) is a central annual  combinatorial meeting with special emphasis on enumerative and algebraic combinatorics. This year it was the 24th such event although I could have swear that I took part in an FPSAC in Montreal already in 1985 but apparently this was a conference with a similar flavor and different name. Much is going on in enumerative and algebraic combinatorics. Cluster algebras, miraculously discovered a decade ago by Fomin and Zelevinsky are going strong in combinatorics as well as in other areas. Alternating sign matrices continue to offer amazing problems and answers. There were quite a few lectures on representation theory, symmetric functions, random matrices, and also on relations of enumerative combinatorics with hyperplane arrangements with polytopes and with physics. There were lectures involving massive computations and new computerized method and packages for symbolic computations  were described. Here are the slides of my lecture entitled Discrete isoperimetry: problems, results, applications and methods. The program page now contains slides for most lectures.

What are alternating sign matrices?

I suppose that you all know what a permutation matrix is (an n by n matrix with 0,1 entries and one non zero entry in each row and each column) and alternating sign matrices are amazing generalization of permutation matrices discovered by William Mills, David Robbins, and Howard Rumsey. (See also this article by Bressoud and Propp) They are integral n by n matrices with 0,1 and -1 entries. In every row and every columns  the non zero aliments (and there must be at least one such element)  should alternate between 1 and -1 and start and end with a ‘1’. Alternating sign matrices are in one to one correspondence with monotone triangle. Thos are triangles of integers starting with a row: 1,2,…,n. With the following rules: (a) all rows are strictly increasing; (b) every element in row i is weakly between the two elements above it.

The amazing thing is that the number of alternating sign matrices of order n is precisely


This was a conjecture by Mills, Robbins and Rumsey and it took over a decade until it was proved by Doron Zeilberger. Later Greg Kuperberg found a short proof and by now several proofs are known. If you have some information or ideas on alternating sign matrices that you would like to share or some questions about them, or about anything else, please contribute a comment.

Satoshi Murai and Eran Nevo proved the Generalized Lower Bound Conjecture.

Satoshi Murai and Eran Nevo have just proved the 1971 generalized lower bound conjecture of McMullen and Walkup, in their  paper On the generalized lower bound conjecture for polytopes and spheres . Let me tell you a little about it. For more background see the post: How the g-conjecture came about.

Face numbers and h-numbers

Let P be a (d-1)-dimensional simplicial polytope and let f_i(P) be the number of i-dimensional faces of P. The fvector (face vector) of P is the vector f(P)=(f_{-1}(P),f_0(P),f_1(P),...).

Face numbers of simplicial d-polytopes  are nicely expressed via certain linear combinations called the h-numbers. Those are defined by the relation:

\sum_{0\leq i\leq d}h_i(P)x^{d-i}= \sum_{0\leq i\leq d}f_{i-1}(P)(x-1)^{d-i}.

What’s called “Stanley’s trick” is a convenient way to practically compute one from the other, as illustrated in the difference table below, taken from Ziegler’s book `Lectures on Polytopes’, p.251:


1           6

1          5            12

1          4           7            8

h= (1        3          3            1)

Here, we start with the f-vector of the Octahedron (1,6,12,8) (bold face entries) and take differences as shown in this picture to end with the h-vector (1,3,3,1).

The Euler-Poincare relation asserts that h_d(P)=(-1)^{d-1}\tilde{\chi}(P)=1=h_0(P). More is true. The Dehn-Sommerville relations state that h(P) is symmetric, i.e. h_i(P)=h_{d-i}(P) for every 0\leq i\leq d.

The generalized lower bound conjecture

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture (GLBC):

Let P be a simplicial d-polytope. Then

(A) the h-vector of P, (h_0,h_1,...,h_d) satisfies h_0 \leq h_1 \leq ... \leq h_{\lfloor d/2 \rfloor}.

(B) If h_{r-1}=h_r for some r \leq d/2 then P can be triangulated without introducing simplices of dimension \leq d-r.

The first part of the conjecture was solved by Stanley in 1980 using the Hard Lefschetz theorem for toric varieties. This was part of the g-theorem that we discussed extensively in a series of posts (II’, II, IIIB). In their paper, Murai and Nevo give a proof of part (B). This is remarkable!

Earlier posts on the g-conjecture:

I: (Eran Nevo) The g-conjecture I

I’ How the g-conjecture came about

II (Eran Nevo) The g-conjecture II: The commutative-algebra connection

III (Eran Nevo) The g-conjecture III: Algebraic shifting

B: Billerafest

Updates, Boolean Functions Conference, and a Surprising Application to Polytope Theory

The Debate continues

The debate between Aram Harrow and me on Godel Lost letter and P=NP (GLL) regarding quantum fault tolerance continues. The first post entitled Perpetual  motions of the 21th century featured mainly my work, with a short response by Aram. Aram posted two of his three rebuttal posts which included also short rejoiners by me. Aram’s first post entitled Flying machines of the 21th century dealt with the question “How can it be that quantum error correction is impossible while classical error correction is possible.” Aram’s  second post entitled Nature does not conspire deals with the issue of malicious correlated errors.  A third post by Aram is coming and  the discussion is quite interesting. Stay tuned. In between our posts GLL had several other related posts like Is this a quantum computer? on how to tell that you really have a genuine quantum computer , and Quantum ground day that summarized the comments to the first post.

Virgin Island Boolean Functions

In the beginning of February I spend a week in a great symposium on Analysis of Boolean Functions, one among several conferences supported  by the Simons foundation, that took place at St. John of the Virgin Islands.

Irit Dinur and me

Ryan O’Donnell who along with Elchanan Mossel and Krzysztof Oleszkiewicz (the team of “majority is stablest” theorem) organized the meeting, live blogged about it on his blog. There are also planned scribes of the lectures and videos. I posed the following problem (which arose naturally from works presented in the meeting): What can be said about circuits with n inputs representing n Gaussian random variables, and gates of the form: linear functions, max and min.

A surprising application of a theorem on convex polytopes.

(Told to me by Moritz Schmitt and Gunter Ziegler)

A theorem I proved with Peter Kleinschmidt and Gunter Meisinger asserts that every rational polytope of dimension d>8 contains a 3-face with at most 78 vertices or 78 facets. (A later theorem of Karu shows that our proof applies to all polytopes.) You would not expect to find a real life application for such a theorem. But a surprising application has just been given.

Before talking about the application let me say a few more words about the theorem. The point is that there is a finite list of 3-polytopes so that every polytope of a large enough dimension (as it turns out, eight or more) has a 3-face in the list. It is conjectured that a similar theorem holds for k-faces, and  it is also conjectured that if the dimension is sufficiently high you can reduce the list to two polytopes: the simplex and the cube. These conjectures are still open. (See this post  for related open problems about polytopes.) For k=2, it follows from Euler’s theorem that every three-dimensional polytope contains a face which is a triangle, quadrangle, or pentagon, and in dimension five and up, every polytope has a 2-face which is a triangle or a rectangle.

Continue reading

Projections to the TSP Polytope

Michael Ben Or told me about the following great paper Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf. The paper solves an old conjecture of Yannakakis about projections of polytopes.

From the abstract: “We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.”

There are many interesting aspects to this story. The starting point was a series of papers in the 80s trying to prove that P=NP by solving TSP using linear programming. The idea was to present the TSP polytope as a projection of a larger dimensional polytope described by  polynomially many linear inequalities, and solve the LP problem on that larger polytope.  Yannakakis proved that such attempts are doomed to fail, when the larger LP problem keep the symmetry of the original TSP polytope.

Yannakakis asked if the symmetry condition can be removed and this is what the new paper shows. This is a very interesting result also from the point of view of convex polytope theory.

Another exciting aspect of the paper is the use of methods from quantum communication complexity.

Update: See this post over GLL for discussion and a description of a follow up paper.


Polymath3 (PHC6): The Polynomial Hirsch Conjecture – A Topological Approach

This is a new polymath3 research thread. Our aim is to tackle the polynomial Hirsch conjecture which asserts that there is a polynomial upper bound for the diameter of graphs of d-dimensional polytopes with n facets. Our research so far was devoted to an abstract combinatorial setting. We studied an appealing conjecture by Nicolai Hahnle and considered an even more general abstraction proposed by Yury Volvovskiy. Comments towards this abstract conjecture are most welcome!

Here, I would like to mention a topological approach which follows a result that was discovered independently by Tamon Stephen and Hugh Thomas in their paper An Euler characteristic proof that 4-prismatoids have width at most 4,
and by Paco Santos in his paper Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids. This post is based on a discussion with Paco Santos at Oberwolfach.

Two maps on a two dimensional Sphere

Theorem: Given a red map and a blue map drawn in general position on S^2 there is an intersection point of two edges of different colors which is adjacent (in the refined map) to a red vertex and to a blue vertex.

Blue and black maps

There are two proofs for the theorem. The proof by Stephen and Thomas uses an Euler characteristic argument. The proof by Santos applies a connectivity argument. Both papers are short and elegant. Both papers point out that the result does not hold for maps on a torus.

Santos’ counterexample to the Hirsch conjecture is based on showing that a direct extension of this result to maps in three dimensions fails. (Even for two maps coming from fans based on polytopes.) Of course, first Paco found his counterexample and then the two-map theorem was found in response to his question  of whether one can find in dimension four counterexamples of the kind he presented in dimension five.

The theorem by Santos, Stephen, and Thomas is very elegant. The proofs are simple but far from obvious and it seems to me that the result will find interesting applications. Its elegance and depth reminded me of Anton Klyachko’s car crash theorem.

A topological question in high dimensions

Now we are ready to present a higher-dimensional analog:

Tentative Conjecture: Let M_1 be a red map and let  M_2 be a blue map drawn in general position on S^{n}, and let $M$ be their common refinement.  There is a vertex w of M a blue vertex v \in M_1, a red vertex u \in M_2 and two faces F,~G \in M such that 1) v,w \in F, 2) w,u \in G, and 3) \dim F + \dim G =n.

A simple (but perhaps not the most general) setting in which to ask this question is with regard to the red and blue maps  coming from red and blue polyhedral fans associated to red and blue convex polytopes. The common refinement will be the fan obtained by taking all intersections of cones, one from the first fan and one from the second.

(Perhaps when n=2k we can even guarantee that \dim F=\dim G=k.)

Why the tentative conjecture implies that the diameter is polynomial

An affirmative answer to this conjecture will lead to a bound of the form dn for the graph of d-polytopes with n facets.

Here is why:

– It is known that the diameter of every polytope with n facets and dimension d is bounded above by the “length” of a Dantzig figure with 2n-2d facets and n-d vertices.

Here a Dantzig figure is a simple polytope of dimension D with 2D facets and two complementary vertices. (i.e., two vertices such that each vertex lies in half of the facets, and they do not belong to any common facet).

The length of the Dantzig figure is the graph distance between these two vertices. This is the classical “d-step theorem” of Klee and Walkup, 1967.

– The length of a Dantzig figure of dimension d is the same as the minimum distance between blue and red vertices in a pair of two maps in the (d-2)-sphere, with d cells each.

– Our tentative conjecture implies, by dimension on d, that the minimum distance between blue and red vertices in a pair of maps in the d-sphere and with n cells is bounded above by (essentially) nd. (n cells means “cells of the blue map plus cells of the red map”, not “cells of the common refinement”).

The abstract setting and other approaches

More comments, ideas, and updates on the abstract setting are of course very welcome Also very welcome are other approaches to the polynomial Hirsch conjecture, and discussion of related problems.

An example showing that the theorem fail for blue and red maps on a torus.

IPAM Remote Blogging: Santos-Weibel 25-Vertices Prismatoid and Prismatoids with large Width

Here is a web page by Christope Weibel on the improved counterexample.

The IPAM webpage contains now slides of some of the lectures. Here are Santos’s slides. The last section contains some recent results on the “width of 5-prismatoids”  A prismatoid is a polytope with two facets containing all the vertices. The width of a prismatoid is the number of steps needed to go between these two facets where in each step we move from a facet to an adjacent one. Santos’s counterexample is based on findng 5-dimensional prismatoid with width larger than 5. It is observed that the width of a 5-prismatoid with n vertices cannot exceed 3n/2 and it is shown (by rather involved constructions) that there are examples where the width is as large as \sqrt n.

Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

Here are some links and posts related to some of the talks in IPAM’s workshop “Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?” I will be happy to add links to pdf’s of the presentations and to relevant papers. Descriptions and remarks on individual lectures are very welcome. In particular you are most welcome to post here the posters/abstract/papers from the poster session. (Because of some technical matters I will have to miss the workshop. I hope to be able somehow to follow it from far away.)

Following is a description of some of the lectures and some useful links for a few lectures:

A counterexample to Hirsch’s conjecture: Posts related to Paco Santo’s lecture (Tuesday morning) describing a counter example to Hirsch’s conjecture are here and here The second post contains a link to Paco’s paper. Fred Holt’s second lecture will describe some new consequence to Paco’s construction. 

Acyclic USO: Acyclic unique sink orientations (Acyclic USO) of cubes and more general polytopes are mentioned in this post about abstract linear objective functions as well as this one about telling simple polytopes from their graphs. Acyclic USO are mentioned discussed in David Avis’s Wednesday morning talk and a few others.

Stochastic games: Stochastic games relevant to Yinyu Ye’s and Oliver Friedmann’s Thursday morning talks are discussed in this post. Some background (and links to the papers) for the new subexponential lower bounds for randomized pivot rules that will be described in Friedmann’s lecture can be found in this post. 

Polynomial Hirsch conjecture: Ed Kim’s (Thursday afternoon) and Nicolai Hähnle’s  (Friday’s morning) talks are related to polymath3. David Bremner will discuss (Tuesday afternoon) the combinatorics and geometry of path complexes. Jonathan Kelner will propose (Friday morning) a geometric/probabilistic method based on smoothed analysis to attack th epolynomial Hirsch conjecture.

Bad behavior of the simplex algorithms. Examples for the bad behavior of simplex type algorithms (mainly in three dimensions) will be described in Günter Ziegler’s talk (Tuesday afternoon). Here is the link to Günter’s slides which are rather detailed. Bernd Gärtner (Wednesday morning) will demonstrate how Goldfarb’s cubes can be used to refute a conjecture regarding an algorithm for machine learning. 

Interior point methods: Since the mid 80s interior point methods for linear programming are as important theoretically and practically as simplex type algorithms. (I will add a link for a good wide-audience description of interior point methods HERE.) Jim Renegar’s Thursday afternoon lecture will describe some new advances on  Central Swaths (a generalization of the central path a central notion for interior point methods. ) Santosh Vampala closing lecture will propose a hybrid vertex-following interior-type algorithm.

Continuous analogs: There are several interesting continuous analogs for combinatorial notions and questions related to the simplex algorithms. Yuriy Zinchenko will discuss (Wednesday afternoon) continuous analogs of the Hirsch conjecture

Walking on the arragements: Consider the entire arrangement of hyperplanes described by the inequalities of an LP problem. The simplex algorithm can be described as a walk on vertices of this arrangements. Those are very special vertices – the vertices of the feasible polyhedron. The dual simplex algorithm can also be described as a walk on vertices of the arrangement. This time the relevant vertices (I think) are dual-feasible, namely those are vertices of the arrangement which optimize the objective function w.r.t. a subset of the inequalities.  What about LP algorithms based on more general type of walks?  Kumei Fukuda Thursday’s afternoon talk will discuss this issue.  

A new polynomial LP algorithm:  Sergei Chubanov (Thursday afternoon) will propose a strongly polynomial relaxation-type algorithm which either finds a solution of a linear system or decides that the system has no 0,1-solutions. If the system is feasible and the bounds on variables are tight, the algorithm always finds a solution. Sergei will continue to show that the algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming. Here is a link to the paper. Tamás Terlaky (Wednesday afternoon) will review several algorithms for linear programming including elimination and pivot algorithms, interior point methods and the perceptron algorithm.

Complexity of Delaunay Triangulation:  Nina Amenta’s Friday talk will describe what we recently learned about the the complexity of Delaunay triangulations as function of the distribution of their vertices, and will raise the question “how much of this can be applied to polytopes in general?”

Among the additional presentations: Christophe Weibel presented an improvement to Paco Santos’ counterexample. Jésus de Loera presented a paper with Bernd Sturmfels, and Cynthia Vinzant on the centeral curve in linear programming.