The Polynomial Hirsch Conjecture: Discussion Thread

polymath3

This post is devoted to the polymath-proposal about the polynomial Hirsch conjecture. My intention is to start here a discussion thread on the problem and related problems. (Perhaps identifying further interesting related problems and research directions.)

Earlier posts are: The polynomial Hirsch conjecture, a proposal for Polymath 3 , The polynomial Hirsch conjecture, a proposal for Polymath 3 cont. , The polynomial Hirsch conjecture – how to improve the upper bounds .

First, for general background: Here is a  chapter that I wrote about graphs, skeleta and paths of polytopes. Some papers on polytopes on Gunter Ziegler’s homepage  describe very interesting and possibly relevant current research in this area,  and also a few of the papers under “discrete geometry” (which follow the papers on polytopes) are relevant. Here are again links for the recent very short paper by  Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss, the 3-pages paper by Sasha Razborov,  and to Eddie Kim and Francisco Santos’s survey article on the Hirsch Conjecture.

Here are the basic problems and some related problems. When we talk about polytopes we usually mean simple polytopes. (Although looking at general polytopes may be of interest.)

Problem 1: Improve the known upper bounds for the diameter of graphs of polytopes, perhaps finding a polynomial upper bound in term of the dimension d and number of facets n.

Strategy 1: Study the problem in the purely combinatorial settings proposed in the EHR paper.

Strategy 2: Explore other avenues.

Problem 2: Improve  the known lower bounds for the problem in the abstract setting.

Strategy 3: Use the argument for upper bounds as some sort of a role model for an example. 

Strategy 4:Try to use recursively mesh constructions as those used by EHR.

Problem 3: What is the diameter of a polytopal digraph for a polytope with n facets in dimension d.

A polytopal digraph is obtained by orienting edges according to some generic linear objective function. This problem can be studied also in the abstract setting of shellability. (And even in the context of unique sink orientations.)

Problem 4: Find a (possibly randomized) pivot rule for the simplex algorithm which requires, in the worse case, small number of pivot steps.

A “pivot rule” refers to a rule to walk on the polytopal digraph where each step can be performed efficiently.

Problem 5: Study the diameter of graphs (digraphs) of specific classes of polytopes. 

Problem 6: Study these problems in low dimensions.

Here are seven additional relevant problems.

Problem 7: What can be said about expansion properties of graphs of polytopes? Continue reading

The Polynomial Hirsch Conjecture – How to Improve the Upper Bounds.

polymath3

I can see three main avenues toward making progress on the Polynomial Hirsch conjecture.

One direction is trying to improve the upper bounds, for example,  by looking at the current proof and trying to see if it is wasteful and if so where it can be pushed further.

Another direction is trying to improve the lower-bound constructions for the abstract setting, perhaps by trying to model an abstract construction on the ideas of the upper bound proof.

The third direction is to talk about entirely different avenues to the problem: new approaches for upper bounds, related problems, special classes of polytopes, expansion properties of graphs of polytopes, the relevance of shellability, can metric properties come to play, is the connection with toric varieties relevant, continuous analogs, and other things I cannot even imagine.

Reading the short  recent paper by  Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss will get you started both for the upper bounds and for the lower bounds.

I want to discuss here very briefly how the upper bounds could be improved. (Several people had ideas in this direction and it would be nice to discuss them as well as new ideas.) First, as an appetizer, the very basic argument described for polytopes. Here \Delta (d,n) is the maximum diameter of the graph of a d-dimensional polyhedron with n facets.

 

 untitled

(Click on the picture to get it readable.)

The main observation here (and also in the abstract versions of the proof) is that

if we walk from a vertex v in all possible directions \Delta(d,k) steps we can reach vertices on at least k+1 facets.

But it stands to reason that we can do better.

Suppose that n is not too small (say n=d^2.). Suppose that we start from a vertex v and walk in all possible directions t steps for

t=\Delta (d,10d)+\Delta (d-1,10d)+\Delta(d-2,10d)+\dots +\Delta(2,10d).  (We can simply take the larget quantity t = d \Delta (d,11d).)

The main observation we just mentioned implies that with paths of this length starting with the vertex v we can reach vertices on 10d facets  and on every facet we reach we can reach vertices on 10d facets and in every facet of a facet we can reach vertices on 10d facets and so on. It seems that following all these paths we will be able to reach vertices on many many more than 10d facets. (Maybe a power greater than one of d or more.)  Unless, unless something very peculiar happens that perhaps we can analyze as well.

The Polynomial Hirsch Conjecture, a Proposal for Polymath3 (Cont.)

The Abstract Polynomial Hirsch Conjecture

pball

A convex polytope P is the convex hull of a finite set of points in a real vector space. A polytope can be described as the intersection of a finite number of closed halfspaces. Polytopes have a facial structure: A (proper) face of a polytope P is the intersection of  P with a supporting hyperplane. (A hyperplane H is a supporting hyperplane of P if P is contained in a closed halfspace bounded by H, and the intersection of H and P is not empty.) We regard the empty face and the entire polytope as trivial faces. The extreme points of a polytope P are called its vertices. The one-dimensional faces of P are called edges. The edges are line intervals connecting a pair of vertices. The graph G(P) of a polytope P  is a graph whose vertices are the vertices of P and two vertices are adjacent in G(P) if there is an edge of P connecting them. The (d-1)-dimensional faces of a polytop are called facets.  

The Hirsch conjecture: The graph of a d-polytope with n  facets has diameter at most n-d.

A weaker conjecture which is also open is:

Polynomial Hirsch Conjecture: Let G be the graph of a d-polytope with n facets. Then the diameter of G is bounded above by a polynomial in d and n.

The avenue which I consider most promising (but I may be wrong) is to replace “graphs of polytopes” by a larger class of graphs. Most known upper bound on the diameter of graphs of polytopes apply in much larger generality. Recently, interesting lower bounds were discovered and we can wonder what they mean for the geometric problem.    

Here is the (most recent) abstract setting:

Consider the collection {\cal G}(d,n) of graphs G whose vertices are labeled by d-subsets of an n element set.

The only condition we will require is that if  v is a vertex labeled by S and u is a vertex labeled by the set T, then there is a path between u and v so that all labels of its vertices are sets containing S \cap T.

Abstract Polynomial Hirsch Conjecture (APHC): Let G \in {\cal G}(d,n)  then the diameter of G is bounded above by a polynomial in d and n.

Everything that is known about the APHC can be described in a few pages. It requires only rather elementary combinatorics; No knowledge about convex polytopes is needed.

A positive answer to APHC (and some friends of mine believe that n^2 is the right upper bound) will apply automatically to convex polytopes.

A negative answer to APHC will be (in my opinion) extremely interesting as well, Continue reading

The Polynomial Hirsch Conjecture: A proposal for Polymath3

pball

This post is continued here. 

Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture.

The Hirsch conjecture: The graph of a d-polytope with n vertices  facets has diameter at most n-d.

We devoted several posts (the two most recent ones were part 6 and part  7) to the Hirsch conjecture and related combinatorial problems.

A weaker conjecture which is also open is:

Polynomial Diameter Conjecture: Let G be the graph of a d-polytope with n facets. Then the diameter of G is bounded above by a polynomial of d and n.

One remarkable result that I learned from the survey paper is in a recent paper by  Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss who proved that: 

Eisenbrand, Hahnle, and Rothvoss’s theorem: There is an abstract example of graphs for which the known upper bounds on the diameter of polytopes apply, where the actual diameter is n^{3/2}.

Update (July 20) An improved lower bound of \Omega(n^2/\log n) can be found in this 3-page note by Rasborov. A merged paper by Eisenbrand, Hahnle, Razborov, and Rothvoss is coming soon. The short paper of Eisenbrand,  Hahnle, and Rothvoss contains also short proofs in the most abstract setting of the known upper bounds for the diameter.

This is something I tried to prove (with no success) for a long time and it looks impressive. I will describe the abstract setting of Eisenbrand,  Hahnle, and Rothvoss (which is also new) below the dividing line.

I was playing with the idea of attempting a “polymath”-style  open collaboration (see here, here and here) aiming to have some progress for these conjectures. (The Hirsch conjecture and the polynomial diameter conjecture for graphs of polytopes as well as for more abstract settings.) Would you be interested in such an endeavor? If yes, add a comment here or email me privately. (Also let me know if you think this is a bad idea.) If there will be some interest, I propose to get matters started around mid-August. 

 Here is the abstract setting of Eisenbrand, Hahnle, and Rothvoss: Continue reading

(Eran Nevo) The g-Conjecture II: The Commutative Algebra Connection

Richard_Stanley-1

Richard Stanley

This post is authored by Eran Nevo. (It is the second in a series of five posts.)

The g-conjecture: the commutative algebra connection

Let K be a triangulation of a (d-1)-dimensional sphere. Stanley’s idea was to associate with K a ring R, and study the relations between algebraic properties of R and combinatorial properties of K.

Face ring

Fix a field k. The face ring (Stanley-Reisner ring) of K over k is k[K]=k[x_{1},..,x_{n}]/I_{K} where I_{K} is the homogenous ideal generated by the monomials whose support is not in K, \{\prod_{i\in S}x_i:\ S\notin K\}. For example, if K is the boundary of a triangle, then k[K]=k[x,y,z]/(xyz). k[K] is graded by degree (variables have degree one, 1 has degree zero), and let’s denote the degree i part by k[K]_i. This part is a finite dimensional k-vector space and we can collect all these dimensions in a sequence, or a series, called the Hilbert series of k[K], which carries the same information as f(K). More precisely,

hilb(k[K]):=\sum_{i\geq 0}\dim_k k[K]_i t^i = \frac{h_0(K)+h_1(K)t+...+h_d(K)t^d}{(1-t)^d}

(recall that K is (d-1)-dimensional).

Cohen-Macaulay (CM) ring

The ring k[K] is called Cohen Macaulay (CM) if there are d elements \Theta=\{\theta_1,..,\theta_d\} in k[K]_1 such that k[K] is a free k[\Theta]-module. As hilb(k[\Theta])=\frac{1}{(1-t)^d}, the numerical consequence is that hilb(k[K]/(\Theta))=h(K) (we use h both as a vector and as a polynomial, with the obvious identification).

Macaulay (revisited) showed that the Hilbert series of standard rings (=quatient of the polynomial ring by a homogenous ideal) are exactly the M-vectors (sequences).

A theorem of Riesner characterizes the simplicial complexes K with a CM face ring over a fixed field k in terms of the homology of K and its face links (with $k$-coefficients). It follows that if K is a simplicial sphere then k[K] is CM, hence h(K) is an $M$ vector! This gives more inequalities on f(K). This is also how Stanley proved the Upper Bound Conjecture, for face number of spheres: It follows that if K is a (d-1)-sphere with n vertices, and C(d,n) is the boundary of the cyclic d-polytope with n vertices, then for every i, f_i(K)\leq f_i(C(d,n)). This is as h_i(K)\leq \binom{n-d+i-1}{i}=h_i(C(d,n)).

Hard Lefschetz

Let K be the boundary of a simplicial d-polytope. Stanley observed that the hard Lefschetz theorem for toric varieties, an important theorem in algebraic geometry, translates in the language of face rings as follows: there exists \Theta as above and \omega\in k[K]_1 such that the maps

w^{d-2i}: (k[K]/(\Theta))_i\rightarrow (k[K]/(\Theta))_{d-i}

are isomorphisms between those vector spaces for any integer 0\leq i\leq \frac{d}{2}. In particular, w: (k[K]/(\Theta))_{i-1}\rightarrow (k[K]/(\Theta))_{i} is injective for 1\leq i\leq \frac{d}{2}. Thus, the quotient ring k[K]/(\Theta, \omega) has Hilbert series starting with g(K). This means, again by Macaulay theorem, that g(K) is an M-vector!

Later, in 1993, McMullen gave a different proof of this part of his conjectured g-theorem. His proof actually proves hard Lefschetz for this case. See McMullen’s survey paper `Polyhedra and polytopes: algebra and combinatorics’.

Problems

Does hard Lefschetz theorem hold for non polytopal spheres?

Can you think of examples of simplicial spheres which cannot be realized as the boundary of convex polytopes?

How the g-Conjecture Came About

This post complements Eran Nevo’s first  post on the g-conjecture

1) Euler’s theorem

euler1

Euler

Euler’s famous formula V-E+F=2 for the numbers of vertices, edges and faces of a  polytope in space is the starting point of many mathematical stories. (Descartes came close to this formula a century earlier.) The formula for d-dimensional polytopes P is

f_0(P)-f_1(P)+f_2(P)+\dots+(-1)^{d-1}f_{d-1}(P)=1-(-1)^d.

The first complete proof (in high dimensions) was provided by Poincare using algebraic topology. Earlier geometric proofs were based on “shellability” of polytopes which was only proved a century later. But there are elementary geometric proofs that avoid shellability.

2) The Dehn-Sommerville relations

Dehn

Consider a 3-dimensional simplicial polytope, – Continue reading

(Eran Nevo) The g-Conjecture I

This post is authored by Eran Nevo. (It is the first in a series of five posts.)

mcmullen

Peter McMullen

The g-conjecture

What are the possible face numbers of triangulations of spheres?

There is only one zero-dimensional sphere and it consists of 2 points.

The one-dimensional triangulations of spheres are simple cycles, having n vertices and n edges, where n\geq 3.

The 2-spheres with n vertices have 3n-6 edges and 2n-4 triangles, and n can be any integer \geq 4. This follows from Euler formula.

For higher-dimensional spheres the number of vertices doesn’t determine all the face numbers, and for spheres of dimension \geq 5 a characterization of the possible face numbers is only conjectured! This problem has interesting relations to other mathematical fields, as we shall see. Continue reading

Ziegler´s Lecture on the Associahedron

j_stasheffdevadoss

 

The associahedron in 3 dimension, and James Stasheff. This picture is taken from Bill Casselman’s article on the associahedron. The article is entitled “Strange Associations” and starts with “There are many other polytopes that can be described in purely combinatorial terms. Among the more curious are the associahedra….”

Dov Tamari as a young student at the Hebrew University of Jerusalem.

The associahedron (also known as the Stasheff polytope) is a remarkable convex polytope first described combinatorially by James Stasheff in 1963. The first proof that it is indeed a polytope is attributed to John Milnor (unpublished). The combinatorial structure was considered independently by Dov Tamari who also asked for a realization as a convex polytope, and such a realization was found by Mark Haiman and Carl Lee. It was also constructed independently as a special case of a much more general construction (called ¨secondary polytopes¨) by Israel Gelfand, Michael Kapranov, and Andrei Zelevinsky.

These are lecture notes from Günter M. Ziegler´s lecture on the associahedron at the ¨DocCourse Combinatorics and Geometry 2009¨at CRM located at at the Autonomous University of Barcelona.

 zelevinsky

4.1 Making polytopes from graphs

We will start with several families of graphs and ask if there is a nice cell structure extending the graph structure, and if this cell structure is the cell structure of  a convex polytope. 

4.1.1 Permutations and the permutahedron

Example I:

The vertices: all permutations on the letters 1,2,… ,n

The edges: Two permutations are adjacent if one is obtained by the other by replacing the location of two adjacent letters.

The number of vertices is n!. The degree of every vertex is n-1.

4.1.2 Bracketing and the associahedron

(or triangulation of polygons with non-crossing diagonals, or binary trees)

Example II:

The vertices correspond to all ways to put brackets in an expression x_1x_2\cdots x_n of n non associative variables.

For example for 4 variables there are 5 vertices corresponding to: ((xy)z)u, (x(yz))u, (xy)(zu), x((yz)u), and x(y(zu)).  Those are in one to one correspondence with all possible triangulations of a 5-gon with noncrossing diagonals, as well as with binary trees with 4 leaves.

The edges are obtained by replacing a subword t(su) by (ts)u.

Note: “subword” of course means that t or s or u could be a word, not just a letter.

The number of vertices is the (n-1)-th Catalan number c_{n-1}=\frac{1}{n}{{2n-2} \choose {n-1}}. The degree of every vertex is n-1.

 4.1.3 Bracketing plus cyclic permutations and –  the cyclohedron

Raoul Bott in 1986

  

Example III:

The vertices: This time you consider all ways to put brackets in a word x_1x_2\cdots x_n as in example II and also in all words obtained as cyclic permutations of this word.

The edges: In addition to the same brackets as in example II you also allow changing the order of terms in the ¨top¨multiplication.

For example, when there are four variables we have 20 vertices. In addition to the type of edges we saw in the associahedron there is an edge also between (xy)(zu) to (zu)(xy) and between ((xy)z)u to u((xy)z).  

Continue reading

Telling a Simple Polytope From its Graph

Peter Mani  (a photograph by Emo Welzl)

Simple polytopes, puzzles

 

Micha A. Perles conjectured in the ’70s that the graph of a simple d-polytope determines the entire combinatorial structure of the polytope. This conjecture was proved in 1987 by Blind and Mani and shortly afterwards I gave a simple proof which I like very much to present. 

Let P and Q be two simple d-dimensional polytopes. Let \psi be a bijection from the vertices of P to the vertices of Q which maps edges to edges. In other words, \psi is an isomorphism between the graph G(P) of P to the graph G(Q) of Q. Does \psi extend uniquely to a combinatorial isomorphism between P and Q? The answer is ‘yes’ but the argument is not so easy. There are also several related open problems.

Eric Friedman

 

A quick reminder about simple polytopes. A d-polytope P is simple if every vertex v of P is contained in d edges. (Equivalently, if the dual polytope P^* is simplicial.) Thus the graph G(P) of a simple d-polytope P is a d-regular graph. The crucial property of simple polytopes that we use is that for every vertex v of P and every collection of k edges of P containing v there is a unique k-face of P which contains v and these k edges.   

Among the famous simple polytopes are the cubes and simplices (in any dimension), polygons in the plane, and the dodecahedron in dimension 3 (but not the icosahedron or octahedron).

More background on polytopes can be found at the end of the post. (It is taken from this post presenting five open problems regarding polytopes.).

Good orderings, unique sink acyclic orientations, and shelling.

Consider a total ordering < of the vertices of a simple d-polytope P .  A vertex v is a local maximum if for every neighbor w of v, w<v. Of course, the maximum vertex in P with respect to the ordering is a local maximum.   An ordering of the vertices of P is called good, if for every face F  of P every local maximum in F is the global maximum in F.

( Just to make it clear: a vertex v in F is a local maximum in F, if for every neighbor w of v in F, w<v. The global maximum in F is the maximum vertex of F with respect to <.)

There are several variations of this notion. Instead of talking about the entire ordering we can talk just about the orientation it induces on edges of the graph. We orient an edge \{v,u\} from v to u if v < u. This is an acyclic orientation of the graph and being good or bad depends only on the orientation. Good orientations are called “unique-sink acyclic orientations”.  Also, as we will mention later, good orderings of the vertices of a simple polytope are closely connected to shelling order on the facets of the dual polytope.

The proof: part I

Let G be the graph of a simple d-polytope P.

The crucial claim

Given an ordering < of the vertices of the polytope  we define the degree of a vertex v, denoted by deg_<(v)  as the number of neighbors of v which are smaller than v with respect to the ordering. Let h_k^< be the number of vertices of degree k. Consider the following expression:

f^< = h_0^< +2 h_1^< + \dots + 2^kh_k^< + \cdots +2^nh_n^<

Continue reading

A Diameter problem (7): The Best Known Bound

 

Our Diameter problem for families of sets

Consider a family \cal F of subsets of size d of the set N={1,2,…,n}.

Associate to \cal F a graph G({\cal F}) as follows: The vertices of  G({\cal F}) are simply the sets in \cal F. Two vertices S and T are adjacent if |S \cap T|=d-1.

For a subset A \subset N let {\cal F}[A] denote the subfamily of all subsets of \cal F which contain A

MAIN ASSUMPTION: Suppose that for every A for which {\cal F}[A] is not empty G({\cal F}[A]) is connected.

We will call a family satisfying this assumption “hereditarily connected”.

MAIN QUESTION:   How large can the diameter of G({\cal F}) be in terms of d and n?

We denote the answer by F(d,n).

For v \in \{1,2,\dots,n\} let {\cal F'}[v] be the family obtained from {\cal F}[\{v\}] by removing v  from every set. Since G({\cal F}[v]) = G({\cal F}' [v]), the diameter of  G({\cal F}[\{v\}]) is at most F(d-1,n-1).

8. A slight generalization

Let {\cal F} be an hereditarily connected family of d-subsets of a set X. Let Y be a subset of X. The length of a path of sets S_1,S_2,\dots, S_t modulo Y  (where |S_i \cap S_{i+1}|=d-1 for every i) is the number of j, 1 \le j <t such that both S_j and S_{j+1} are subsets of Y. (In other words, in G({\cal F}) we consider edges between subsets of Y as having length 1 and other edges as having length 0.)

Let T(d,n) be the largest diameter of an hereditarily connected family of d-subsets of an arbitrary set X modulo a set Y , Y \subset X with |Y|=n.

Since we can always take X=Y we have F(d,n) \le T(d,n).  

9.  A quasi-polynomial upper bound

We will now describe an argument giving a quasi-polynomial upper bound for T(d,n). This is an abstract version of a geometric argument of Kleitmen and me. 

Let {\cal F} be a hereditarily connected family of d-subsets of some set X, let Y \subset X, |Y|=n, and let S and T be two sets in the family.

Claim: We can always either

1) find paths of length at most T(d,k)  modulo from S to d-subsets of Y whose union has more than k elements.

or

2) we can find a path of this length T(d,k)  modulo Y   from S to T.  

Proof of the claimLet Z be the set of elements from Y that we can reach in T(d,k) steps modulo Y   from S. (Let me explain it better: Z is the elements of Y in the union of all sets that can be reached in T(d,k) steps modulo Y from S. Or even better: Z is the intersection of Y with the union of all sets in \cal F which can be reached from S in T(d,k) steps modulo Y. ) 

The distance of S from T modulo Z  is at most T(d,|Z|).

Now, if |Z|>k we are in case 1).

If |Z| \le k then there is a path from S to T modulo Z of length T(d,k). If this path reaches no set containing a point in Y \backslash Z we are in case 1).  (Because this path is actually a path of length T(d,k) from S to T modulo Y).  Otherwise, we reached via a path of length T(d,k) modulo Y from S a set containing a point in Y \backslash Z, in contradiction to the definition of Z.  Walla.

Corollary: T(d,n) \le 2T(d,n/2)+T(d-1,n-1).

By a path of length T(d,n/2) modulo Y  we reach from S at least n/2 elements in Y, (or T).  By a path of length T(d,n/2) modulo Y  we reach from T at least n/2 elements in Y, (or S). So unless we can go from S to T in T(d,n/2) steps modulo Y  we can reach more than n/2 elements from both S and T by paths of length T(d,n/2) modulo Y ,hence there is some element we can reach from both.

In other words in T(d,n/2) steps modulo Y  we go from S to S' and from T to T' so that S' and T' share an element u.

But the distance from S' to T' modulo Y  (which is the same as the distance modulo Y  from S' \backslash u to T' \backslash u in {\cal F}'[\{u\}] is at most T(d-1,n-1).  (We use here the fact that u \in Y) Ahla!

To solve the recurrence, first for convenience replace T(d-1,n-1) by T(d-1,n). (You get a weaker inequality.) Then write G(d,n)=T(d,2n) to get G(d,n) \le G(d,n/2)+G(d-1,n) and H(d,x)=G(d,2^x) to get H(d,x) \le H(d-1,x) + H(d,x-1) which gives H(d,x) \le {{d+x} \choose {d}} which in turn gives G(d,n) \le {{log n+d} \choose {d}} and T(d,n) \le n {{log n +d} \choose {d}}. Sababa!

Continue reading