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

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

A Diameter Problem (6): Abstract Objective Functions

Dantzig and Khachyan

George Dantzig and Leonid Khachyan

In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for these directed graphs are the directed graphs of polytopes where the direction of the edges is described by a linear objective function.  

7. Linear programming and the simplex algorithm.

Our diameter problem for families of sets was based on a mathematical abstraction (and a generalization) of the Hirsch Conjecture which asserts that the diameter of the graph G(P) of a d-polytope P with n facets is at most n-d. Hirsch, in fact, made the conjecture also for graphs of unbounded polyhedra – namely the intersection of n closed halfspaces in R^d. But in the unbounded case, Klee and Walkup found a counterexample with diameter n-d+ [d/5]. The abstract problem we considered extends also to the unbounded case and  n-d+ [d/5] is the best known lower bound for the abstract case as well. It is not known if there is a polynomial (in terms of d and n) upper bound for the diameter of graphs of d-polytopes with n facets.

Hirsch’s conjecture was motivated by the simplex algorithm for linear programming.  Let us talk a little more about it: Linear programming is the problem of maximizing a linear objective function \phi(x)=b_1x_1+ b_2 x_2 \dots +b_dx_d subject to a system of n linear inequalities in the variables x_1,x_2,\dots,x_d.

 a_{11}x_1 + x_{12}x_2 + \dots + x_{1d}x_d \le c_1,

a_{21}x_1 + x_{22}x_2 + \dots + x_{2d}x_d \le c_2,

a_{n1}x_1 + x_{n2}x_2 + \dots + x_{nd}x_d \le c_n,

The set of solutions to the system of inequalities is a convex polyhedron. (If it is bounded it is a polytope.)  A linear objective function makes a graph of a polytope (or a polyhedron) into a digraph (directed graph). If you like graphs you would love digraphs, and if you like graphs of polytopes, you would like the digraphs associated with them.  

The geometric description of Dantzig’s simplex algorithm is as follows: the system of inequalities describes a convex d-dimensional polyhedron P. (This polyhedron is called the feasible polyhedron.) The maximum of \phi is attained at a face F of P. We start with an initial vertex (extreme point) v of the polyhedron and look at its neighbors in G(P). Unless v \in F there is a neighbor u of v that satisfies \phi(u) > \phi (v). When you find such a vertex move from v to u and repeat!

8. Abstract objective functions and unique sink orientation.

Let P be a simple d-polytope and let \phi be a linear objective function which is not constant on any edge of the polytope. Remember, the graph of P, G(P) is a d-regular graph. We can now direct every edge u,v from u to v if \phi (v) > \phi (u). Here are two important properties of this digraph.

(AC) It is acyclic! (no cycles)

(US’) It has a unique SINK, namely a unique vertex such that all edges containing it are directed towards it.

The unique sink property is in fact the property that enables the simplex algorithm to work!

When we consider a face of the polytope F and its own graph G(F) then again our linear objective function induces an orientation of the edges of G(F) which is acyclic and also has the unique sink property. Every subgraph of an acyclic graph is acyclic. But having the unique sink property for a graph does not imply it for a subgraph. We can now describe the general unique sink properties of digraphs of polytopes:

(US) For every face F of the polytope, the directed graph induced on the vertices of F has a unique sink.

A unique sink acyclic orientation of the graph of a polytope is an orientation of the edges of the graph which satisfies properties (AC) and (US). 

An abstract objective function of a d-polytope is an ordering < of the vertices of the polytope such that the directed graph obtained by directing an edge from u to v if  u<v is a unique sink acyclic orientation. (Of course, coming from an ordering the orientation is automatically acyclic.) 

Continue reading

A Diameter Problem (5)

6. First subexponential bounds. 

Proposition 1: F(d,n) \le F_k(d,n) \times F(d-k,n-k).

How to prove it: This is easy to prove: Given two sets S and T in our family \cal F, we first find a path of the form S=S_0, S_1, S_2, \dots, S_t = T where, |S_{i-1} \cap S_i| \ge k and t \le F_k(d,n). We let B_i \subset (S_{i-1} \cap S_i ) with |B_i|=k and consider the family {\cal F}'[B_i]. This is a family of (d-k)-subsets of an (n-k) set (N \backslash B_i) . It follows that we can have a path from S_{i-1} to S_i in  G({\cal F}[B_i]) of length at most F(d-k,n-k). Putting all these paths together gives us the required result. (We remind the notations at the end of this post.)

How to use it: It is not obvious how to use Proposition 1. Barnette’s argument from part 3 was about k=1, and it used something a bit more sophisticated. Applying Proposition 1 directly for k=1 does not give anything non trivial. However, when n is small compared to d and k is a small fraction of d we can say something.

Let us start with an example: n = 3d. let us choose k= d/4. Consider a path S=S_0,S_1,\dots S_t=T in G({\cal F}) from two sets S and T. Suppose also that in this path 

(*) S_i \cap T \subset S_{i+1}\cap T, for every i

Let U_1 be the last set in the path whose intersection with S has at least d/4 elements.  Let U_2 be the last set in the path whose intersection with U_1 has at least d/4 elements. I claim that S, U_1, U_2, T is a path in G_{d/4}({\cal F}).

To see this Continue reading

Diameter Problem (4)

Let us consider another strategy to deal with our diameter problem. Let us try to associate other graphs to our family of sets.

Recall that we consider a family \cal F of subsets of size d of the set N= \{ 1,2,\dots, n \}.

Let us now associate  more general graphs to \cal F as follows: For an integer k 1 \le k \le d define G_k({\cal F}) as follows: The vertices of  G_k({\cal F}) are simply the sets in \cal F. Two vertices S and T are adjacent if |S \cap T| \ge k. Our original problem dealt with the case k=d-1.  Thus, G({\cal F}) = G_{d-1}({\cal F}). Barnette proof presented in the previous part refers to G_1({\cal F}) and to paths in this graph.  

As before for a subset A \subset N let {\cal F}[A] denote the subfamily of all subsets of \cal F which contain A. Of course, the smaller k is the more edges you have in G_k({\cal F}). It is easy to see that assuming that G_1({\cal F[A]}) is connected for every A for which {\cal F}[A] is not empty already implies our condition that G({\cal F[A]}) is connected for every A for which {\cal F}[A] is not empty.

Let F_k(d,n) be the maximum diameter of G_k({\cal F})  in terms of k,d and n, for all families \cal F of d-subsets  of N satisfying our connectivity relations.

Here is a simple claim:

F(d,n) \le F_k(d,n) \times F(d-k,n-k).

Can you prove it? Can you use it? 

Diameter Problem (3)

3. What we will do in this post and and in future posts

We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply to the diameter of graphs of simple d-polytopes.

All the methods I am aware of for providing upper bounds are fairly simple.

(1) You think about a strategy from moving from one set to another, 

(2) You use this strategy to get a recursive bound,

(3) You solve the recursion and hope for the best.

What I would like you to think about, along with reading these posts, is the following questions:

(a) Can I come up with a different/better strategy for moving from one set to the other?

(b) Can I think about a mathematically more sophisticated way to get an upper bound for the diameter?

(c) Can this process of finding a strategy/writing the associated recurrence/solving the recurrence be automatized? The type of proofs we will describe are very simple and this looks like a nice example for a “quasi-automatic” proof process.

Let me repeat the problem and prove to you a nice upper bound:

Reminder: 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.

Continue reading