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.

Remarks:

1) The recurrence relation gives $f(n)\le n^{\log n+1}$. The major task is to prove a polynomial upper bound for $f(n)$ or to find examples showing that $f(n)$ is superpolynomial in $n$.

2) 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. 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}$.

3) $f(d,n)$ (and thus also $f(n)$) are upper bounds for the diameter of graphs of d-polytopes with n facets.