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.

Let’s call the maximum t, f(n).

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.

Remarks:

1) The abstract setting is taken from the paper by Eisenbrand, Hahnle, Razborov, and Rothvoss (EHRR). We can consider families of d-subsets of {1,2,…, n}, and denote the maximum cardinality t by $f(d,n)$ . The argument above gives the relation $f(d,n) \le 2f(d,n/2)+f(d-1,n-1)$ , which implies $f(d,n)\le n{{\log n+d}\choose{\log n}}$ $\le n^{\log d+1}$ .

2) $f(d,n)$ (and thus also $f(n)$ ) are upper bounds for the diameter of graphs of d-polytopes with n facets. Let me explain this and also the relation with another abstract formulation. Start with a $d$ -polytope with $n$ facets. To every vertex v of the polytope associate the set $S_v$ of facets containing $v$ . Starting with a vertex $w$ we can consider ${\cal F}_i$ as the family of sets which correspond to vertices of distance $i+1$ from $w$. So the number of such families (for an appropriate $w$ is as large as the diameter of the graph of the polytope. I will explain in a minute why condition (*) is satisfied.

3) For the diameter of graphs of polytopes we can restrict our attention to simple polytopes namely for the case that all sets $S_v$ have size $d$ .

4) Why the families of graphs of simple polytopes satisfy (*)? Because if you have a vertex $v$ of distance $i$ from $w$ , and a vertex $u$ at distance $k>i$ . Then consider the shortest path from $v$ to $u$ in the smallest face $F$ containing both $v$ and $u$ . The sets $S_z$ for every vertex $z$ in $F$ (and hence on this path) satisfies $S_v\cap S_u \subset S_z$ . The distances from $w$ of adjacent vertices in the shortest path from $v$ to $u$ differs by at most 1. So one vertex on the path must be at distance $j$ from $w$ .

5) EHRR considered also the following setting: consider a graph whose vertices are labeled by $d$ subsets of {1,2,…,n}. Assume that for every vertex v labelled by S(v) and every vertex u labelled by S(u) there is a path so that all vertices are labelled by sets containing $S(v)\cap S(u)$ . Note that having such a labelling is the only properties of graphs of simple $d$ -polytopes that we have used in remark 4.