# 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