Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I fixed an obvious typo –  Tony Huynh Sep 30 '10 at 1:45
    
Thanks, Tony!!! –  Gil Kalai Sep 30 '10 at 1:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.