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