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<j<k, 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.

We had many posts related to the Hirsch conjecture.

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.

Continue reading