A combinatorial version for the polynomial Hirsch conjecture
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 &lt;= 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 &lt; 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.