3
$\begingroup$

Given a finite set $S$ with $n$ elements, and a fixed small $k$ (say $k=3$), how to find $k$ linear orders $\leq_1, \dots, \leq_k$ on $S$, such that the number of feasible subsets of $S$ is asymptotically maximal. Here a set $X\subseteq S$ is feasible if it is obtained as an intersection of initial intervals of those orders, that is $$ X = \bigcap_{i=1, \dots, k} \{x\leq_i x_i\} $$ for some $\{x_i\}$.

By asymptotically maximal I mean that the number of feasible subsets $N_{n,k}=c_k n^k + o(n^k)$ as $n \rightarrow\infty$, and that I am interested in $c_k$ (and in the structure of corresponding orders).

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.