Polymath 3: Polynomial Hirsch Conjecture

I would like to start here a research thread of the long-promised Polymath3 on the polynomial Hirsch conjecture.

I propose to try to solve the following purely combinatorial problem.

Consider t disjoint families of subsets of {1,2,…,n}, $F_1, F_2, ..., F_t$.

Suppose that

(*) For every $i, and every $S \in F_i$ and $T \in F_k$, there is $R\in F_j$ which contains $S\cap T$.

The basic question is: How large can t  be???

(When we say that the families are disjoint we mean that there is no set that belongs to two families. The sets in a single family need not be disjoint.)

In a recent post I showed the very simple argument for an upper bound $n^{\log n+1}$. The major question is if there is a polynomial upper bound. I will repeat the argument below the dividing line and explain the connections between a few versions.

A polynomial upper bound for $f(n)$ will imply a polynomial (in $n$) upper bound for the diameter of graphs of polytopes with $n$ facets. So the task we face is either to prove such a polynomial upper bound or give an example where $t$ is superpolynomial.

The abstract setting is taken from the paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle,  Sasha Razborov, and Thomas Rothvoss. They gave an example that $f(n)$ can be quadratic.

Remark: The comments for this post will serve both the research thread and for discussions. I suggested to concentrate on a rather focused problem but other directions/suggestions are welcome as well.

The Polynomial Hirsch Conjecture: The Crux of the Matter.

Consider t disjoint families of subsets of {1,2,…,n}, $F_1, F_2, ..., F_t$.

Suppose that (*) For every $i, and every $S \in F_i$ and $T \in F_k$, there is $R\in F_j$  which contains $S\cap T$

The basic question is: How large can t  be???

Remark: If you restrict your attention  to sets in these families containing an element m and delete m from all of them, you get another example of such families of sets, possibly with smaller value of t. (Those families which do not include any set containing m will vanish.)

Theorem: $f(n)\le f(n-1)+2f(n/2)$.

Proof: Consider the largest s so that the union of all sets in $F_1,...,F_s$ is at most n/2.   Clearly, $s \le f(n/2)$.
Consider the largest r so that the union of all sets in $F_{t-r+1},...,F_t$ is at most n/2.   Clearly, $r\le f(n/2)$.

Now, by the definition of s and r, there is an element m shared by a set in the first s+1 families and a set in the last r+1 families. Therefore (by (*)), when we restrict our attention to the sets containing ‘m’ the families $F_{s+1},...,F_{t-r}$ all survive. We get that $t-r-s\le f(n-1)$. Q.E.D.

Francisco Santos Disproves the Hirsch Conjecture

A title and an abstract for the conference “100 Years in Seattle: the mathematics of Klee and Grünbaum” drew a special attention:

Title: “A counter-example to the Hirsch conjecture”

Author: Francisco Santos, Universidad de Cantabria

I have been in Seattle only once, in January 2002, when I visited to give a colloquium talk at UW. Although Victor Klee was already retired–he was 76 years old–he came to the Department of Mathematics to talk to me. We had a nice conversation during which he asked “Why don’t you try to disprove the Hirsch Conjecture”?

I have later found out that he asked the same question to many people, including all his students, but the question and the way it was posed made me feel special at that time. This talk is the answer to that question. I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the $d$-step theorem of Klee and Walkup.

Great news! Congratulations Paco!

Hirsch’s conjecture (1957) states that the  graph of a d-dimensional polytope with n facets  has diameter no more than nd. That is, any two vertices of the polytope may be connected to each other by a path of at most nd edges.

We had quite a few posts regarding the Hirsch conjecture and related problems.

The Polynomial Hirsch Conjecture: Discussion Thread, Continued

Here is a  link for the just-posted paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle,  Sasha Razborov, and Thomas Rothvoss.

And here is a link to the paper  by Sandeep Koranne and Anand Kulkarni “The d-step Conjecture is Almost true”  – most of the discussion so far was in this direction.

We had a long and interesting discussion regarding the Hirsch conjecture and I would like to continue the discussion here.

The way I regard the open collaborative efforts is as an open collective attempt to discuss and make progress on the problem (and to raise more problems), and also as a way to assist people who think or work (or will think or will work) on these problems on their own.

Most of the discussion in the previous thread was not about the various problems suggested there but rather was about trying to prove the Hirsch Conjecture precisely! In particular, the approach of Sandeep Koranne and Anand Kulkarni which attempts to prove the conjecture using “flips” (closely related to Pachner moves, or bistaller operations) was extensively discussed.  Here is the link to another paper by Koranne and Kulkarni “Combinatorial Polytope Enumeration“. There is certainly more to be understood regarding flips, Pachner moves, the diameter, and related notions. For example, I was curious about for which Pachner moves  “vertex decomposibility” (a strong form of shellability known to imply the Hirsch bound) is preserved. We also briefly discussed metric aspects of the Hirsch conjecture and random polytopes.

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. Here is a  link to Eddie Kim and Francisco Santos’s survey article on the Hirsch Conjecture.

Here is a link from the open problem garden to the continuous analog of the Hirsch conjecture proposed by Antoine Deza, Tamas Terlaky, and  Yuriy Zinchenko.

(Eran Nevo) The g-Conjecture III: Algebraic Shifting

This is the third in a series of posts by Eran Nevo on the g-conjecture. Eran’s first post was devoted to the combinatorics of the g-conjecture and was followed by a further post by me on the origin of the g-conjecture. Eran’s second post was about the commutative-algebra content of the conjecture. It described the Cohen-Macaulay property (which is largely understood and known to hold for simplicial spheres) and the Lefshetz property which is known for simplicial polytopes and is wide open for simplicial spheres.

The g-conjecture and algebraic shifting

Squeezed spheres

Back to the question from last time, Steinitz showed that

any simplicial 2-sphere is the boundary of a convex 3-polytope.

However, in higher dimension

there are many more simplicial spheres than simplicial polytopes,

on a fixed large number of vertices. Continue reading

The Polynomial Hirsch Conjecture: Discussion Thread

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.)

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.

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.

(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

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

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