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 knownThe 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 Friedrich Eisenbrand, Nicolai Hähnle, Sasha Razborov, and Thomas Rothvoss. The quadratic lower bound as well as a proof of the upper bound can be found in their paper.MotivationEvery 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$.MoreThis 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.
A combinatorial version for the polynomial Hirsch conjecture
co.combinatorics;cg.comp geom;open problem;linear programming