Polynomial Hirsch Conjecture

A natural project to try in the polymath+AI setting is the polynomial Hirsch conjecture that we studied in polymath 3.

The Polynomial Hirsch Conjecture – background

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.

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

Let us denote the answer by D(d,n).

It is convenient to view the problem in terms of simplicial complexes.
Let K be the (pure) simplicial complex generated by the family \cal F. In this language, the elements of [n] are the vertices, and the sets in \cal F are the facets. Connectivity of G({\cal F}) is referred to as strong connectivity of K and the condition above asserts that the links of all faces in K are strongly connected.

The conjecture

The Polynomial Hirsch Conjecture (PHC) asserts that D(d,n) is bounded from above by polynomial function of d and n.

No superlinear lower bounds are known for D(d,n). This problem arises naturally from the study of the diameter of graphs of polytopes.

Connection with polytopes

If P is a simplicial d-dimensional polytope with n vertices, then the set of facets of P can be regarded as  family \cal F of d-subsets of [n].  In this case, the dual polytope Q=P^* is a simple polytope with n facets. The graph of G({\cal F}) can be viewed as the graph of Q. The classical Hirsch conjecture asserted that this diameter is at most n-d. This conjecture was disproved in 2010 by Paco Santos, but the possibility that the diameter is bounded by a polynomial in n and d remains open.

A proposed (vague) strategy

An important ingredient in the current upper bounds is the observation that, starting from a set S in the family, we can reach in D(d,m) steps either:

  • sets in the family whose union contains more than m elements of [n], or
  • all sets in the family.

The way this observation is used is the following. Given two sets in the family, we reach in D(d,n/2) steps from each of them two sets (respectively) that contain a common element of [n]. To derive a recursion we then start from scratch in the link of that element.
This “starting from scratch’’ step is the main source of inefficiency in the current arguments.

One early idea raised in the study of the problem was that by

D(d,m_1)+D(d-1,m_2)+D(d-2,m_3)+\cdots

steps we can reach more than m_1^* elements of [n], and in every link of those elements more than m_2^*  elements of [n], and in every link of every reached pair we can reach more than m_3^* elements of [n], and so on.

(When we say that we can reach more than m^* elements in a certain link, this means that we can either reach sets in the link containing more than m vertices, or we reach all facets in that link.)

It seems that either:

  • we reach many vertices altogether already when the m_i are small, which would lead to improved upper bounds; or
  • we repeatedly reach the same vertices, which (hopefully) implies that the subcomplex spanned by the vertices within reach has useful connectivity properties.

Remarks and links

In 2008 I wrote here a series of posts about the problem.
(The above formulation is taken from the first post in the series.)

  • The second post explained the connection with polytopes.
  • The third post showed linear upper bounds for fixed dimensions.
  • The fourth post described a strategy for approaching the problem.
  • The fifth post explained how to implement that strategy.
  • The sixth post discussed connections with abstract objective functions.
  • The seventh post described the best known upper bounds.

In 2020-2011 we ran here polymath3 devoted to the PHC. It was based on an even more general problem about families of subsets and submultisets (=monomials). This greater level of abstraction was introduced in the paper:

Diameter of Polyhedra: The Limits of Abstraction by Freidrich, Hahnle, Razborov, and Rothvoss. 

There were six research threads. (post 1, post 2, post 3, post 4, post 5, post 6).

For this more general combinatorial problem (for monomials) quadratic lower bounds are known.   

A challenge (perhaps not difficult):

The setting above is a large abstraction of the problem for simplicial polytopes. It is known that the problem for general polytopes can be reduced to the simplicial case, but it would be preferable to find an abstraction that directly covers the non-simplicial case.

Challenge: Find a more general settings where the families of sets and monomials will be replaced by families of rank d elements in large classes of atomic lattice.

Leave a comment