Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. 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 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.

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.

share|improve this question
    
Hirsch conjecture, wikipedia –  vzn Sep 25 '12 at 17:14
    
seems like this conjecture would be very testable with & maybe even susceptible to a computational/empirical/experimental approach using a monte carlo method. has anybody tried that? –  vzn Sep 25 '12 at 21:38
    
re your new bounty reason "the current answers are out-of-date & require revision given recent changes" it seems like you have something particular in mind...? this 2013 paper Recent Progress on the Diameter of Polyhedra and Simplicial Complexes by Santos says the Hirsch conjecture is "now disproved". –  vzn Jan 3 at 17:54
    
Dear vzn, This was a sort of joke: any statement on the current answers is correct given that there are no answers. –  Gil Kalai Jan 4 at 20:06
add comment

1 Answer

A friend of mine and me have decided to try the brute-force method and compute some values of $t$ for small values of $n$ and $d$. This is totally impossible without employing pruning, and we hope that the tricks we have found will give some insight in the rest of the problem. So far, we have not managed to get the doubly-exponential running time of the brute force method down significantly (roughly $3^{2^n}$ is our best bound so far) and hence we have not yet reached our original goal of somehow predicting the function behind $f$ from its first few values. We have also not studied all the comments of the previous threads in detail, so some of this may already be known - we basically had fun making our code fast and wanted to post our results somewhere, if I had a functioning LaTeX environment I would have put this on the ArXiV.

Code (it's not exactly production code...): http://pastebin.com/bSetW8JS. Values:

f(d=2, n)=2n-1 for n <= 6

f(d=3, n=3) = 6
{} {0} {01} {012} {12} {2}

f(d=4, n=4) = 8
f(d=3, n=4) = 8
{} {0} {01} {1,02,03} {2,13} {123} {23} {3}
{} {0} {01} {2,013} {1,02,03} {023} {23} {3}

f(d=5, n=5) = 11
f(d=4, n=5) = 11
f(d=3, n=5) = 11
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {012,3} {02,12,013,014} {13,023,04,124} {123,024} {23,24} {234} {34} {4}
{} {0} {01} {012,13} {02,12,013} {03,123,014,024} {023,124} {23,24} {234} {34} {4}

We say that the sequence ${\cal F}_1, ..., {\cal F}_t$ is convex if (*) holds. Our approach constructs convex sequences by appending families to shorter convex sequences, essentially using that if ${\cal F}_1, ..., {\cal F}_t$ is convex, then ${\cal F}_1, ..., {\cal F}_{t-1}$ is convex. We note that ${\cal F}_1, ..., {\cal F}_t$ is convex if and only if for all $A \in {\cal F}_t$ we have that ${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$ is convex. We say that $A$ is compatible with ${\cal F}_1, ..., {\cal F}_{t-1}$ if ${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$ is convex - we save computation time by computing the sets that are compatible with a sequence and then taking the elements of their powerset as the new ${\cal F}_t$, rather than determining if ${\cal F}_1, ..., {\cal F}_t$ is convex directly.

Our next speedup is essentially dynamic programming. We try to find an equivalence relation $\sim$ on convex sequences with the following two properties. First, if ${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$ for two convex sequences, then $A$ is compatible with ${\cal F}_1, ..., {\cal F}_t$ if and only if it is compatible with ${\cal F}'_1, ..., {\cal F}'_t$. Second, if ${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$ and ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$ is convex, then ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1} \sim {\cal F}'_1, ..., {\cal F}'_t, {\cal F}_{t+1}$. Furthermore, we would like it if we can determine whether a set is compatible with elements from an equivalence class, and determine a representative of the equivalence class of ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$ given ${\cal F}_{t+1}$ and a representative of the equivalence class of ${\cal F}_1, ..., {\cal F}_t$. The ensuing dynamic programming algorithm is then obvious. The number of equivalence classes (along with the time taken by the above two operations) then gives a bound on the running time of the obvious dynamic programming algorithm.

For the equivalence we use to get our bound, we use a characterization of convexity that is based on `intervals' as follows. Given a subset $A$ of $\{ 1, \dots, n \}$, we say $A$ is contiguous with respect to a (not necessarily convex) sequence ${\cal F}_1, ..., {\cal F}_t$ if $\{ k \mid \exists B \in {\cal F}_k : A \subseteq B \} = \{ i, \dots, j \}$ for some integers $1 \leq i \leq j \leq n$. We say that $(i, j)$ is the interval for $A$ w.r.t. this sequence. It is easily seen that ${\cal F}_1, ..., {\cal F}_t$ is convex if and only if all subsets of $\{ 1, \dots, n \}$ are contiguous with respect to the sequence.

Now, given a convex sequence ${\cal F}_1, ..., {\cal F}_t$, we mark all subsets of $\{ 1, \dots, n \}$ as not touched, disallowed or active as follows: all elements of ${\cal F}_t$ are active, all elements of ${\cal F}_1, ..., {\cal F}_{t-1}$ are disallowed and all supersets $B$ of sets $A$ whose interval with respect to ${\cal F}_1, ..., {\cal F}_{t-1}$ is $(i, j)$ with $j < t - 1$ are also disallowed. It is immediate that a set $A$ is compatible with the sequence if and only if it is marked as not touched. We define two sequences as equivalent under $\sim$ if their marking is equal. It is easily seen that this equivalence relation satisfies our two properties. For computing whether a set $B$ should be disallowed by the interval condition, we can use the equivalent condition 'there exists a set $C \in {\cal F}_t$ such that for no set $D \in {\cal F}_{t+1}$, $B \cap C \subseteq D$'. $3^{2^n}$ is an immediate bound on the number of equivalence classes.

We also use various extra prunings. We only consider antichains for ${\cal F}_{t+1}$ and we require that the elements of its elements come from ${1, \dots, i}$. Lastly, we use the optimization that ${\cal F}_1 = \{ \{ 1 \} \}, {\cal F}_2 = \{ \{ 1, 2 \} \}$ for optimally long sequences (and similar for ${\cal F}_{t-1}$ and ${\cal F}_t$). We imagine that investigating the behaviour of ${\cal F}_3$ may result in more drastic savings.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.