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:
How large can t be???
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.
Updates
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.
