# A Combinatorial Abstraction 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 on MO in spite it being an open problem. If the project will lead to specific subproblems I (or others) may try asking them also on MO.

### Multisets

One important extension of the problem is to consider families of multisets and not only family of sets. We also restrict our 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.

### Hahnle's conjecture

Nicolai Hahnle proposed the following:

Hahnle's Conjecture: $$f^*(d,n)=d(n-1)+1.$$

### d=3

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

There have been altogether six rsearch threads. Most research dealt with the abstract combinatorial question mentioned above. The last thread dealt with a geometric conjecture (which deserved a separate MO question A-question-about-a-blue-fan-and-a-red-fan-and-their-common-refinement.

• I fixed an obvious typo – Tony Huynh Sep 30 '10 at 1:45