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