# A combinatorial version for the polynomial Hirsch conjecture

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .

Suppose that

(*)

For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, there is $S \in {\cal F}_j$ which contains $R \cap T$.

The basic question is:

## What is known

The best known upper bound is quasi polynomial $t \le n^{\log n+1}$.

The best known lower bound is (up to a logarithmic factor) quadratic.

This abstract setting is taken from the paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle, Sasha Razborov, and Thomas Rothvoss. The quadratic lower bound as well as a proof of the upper bound can be found in their paper.

## Motivation

Every upper bound will apply to the diameter of graphs of d-dimensional polytopes with n facets. To see this associate to every vertex $v$ the set $S_v$ of facets containing it. Then starting from a vertex $w$ let ${\cal F}_r$ be the sets corresponding to vertices of the polytope of distance $r+1$ from $w$.

## More

This problem is the subject matter of polymath3. But I thought it can be useful to present it here and on MO in spite it being an open problem. If the project will lead to specific subproblems I (or others) may try asking them as well.

(Update; Oct 5:) One specific problem that is of special interest is to restrict attention to sets of size d. Let f(d,n) be the maximum value of t when all sets in all families have size d. Let f*(d,n) be the maximim value of t when we allow multisets of size d. Understanding f*(3,n) may be crucial.

Problem: Does f*(3,n) behaves like 3n or like 4n?

The known lower and upper bounds are 3n-2 and 4n-1 respectively. and since the 3 is the beggining of the sequence 'd' while the 4 is the beginning of the sequence $2^{d-1}$ deciding if the truth is 3 or 4 nay be of importance. See the second thread.

-
Hirsch conjecture, wikipedia –  vzn Sep 25 '12 at 17:14
seems like this conjecture would be very testable with & maybe even susceptible to a computational/empirical/experimental approach using a monte carlo method. has anybody tried that? –  vzn Sep 25 '12 at 21:38