Constructing a k-perfect permutations family

Question

I'm looking for a set of permutations over $n$ elements $\mathcal{P}=\{P_1,P_2,...,P_r\}$ of minimal size such that for every ordered subset of size $k$, $S=<x_1,x_2,...,x_k>, (x_i \in [n])$, there exists a permutation $P \in\mathcal{P}, $ such that $P(x_1)<P(x_2)<...<P(x_k)$.

A simple probabilistic argument can show that such family of size $r=k!\cdot k\cdot log(n)+1$ exists:

Suppose we draw $r$ random permutations. The chance that some specific $<x_1,...,x_k>$ is not ordered by non of the permutations is $(1-\frac{1}{k!})^r$.

Using the union bound, the chance that any ordered k tuple will not be ordered is bounded by:

$(1-\frac{1}{k!})^r\cdot$$ n\choose k$$\cdot k!<(1-\frac{1}{k!})^r\cdot n^k < n^k\cdot e^{-r/k!}$

If we demand that the probability will be less than 1 (which ensures such family exists), we get the desired size, $r>k!\cdot k\cdot log(n)$.

The question is:

Is there an explicit build for such family? is it computable in $O(k!\cdot poly(n))$ time?

This question might have been referred to somewhere in a different name, so if anyone is familiar with it, a reference will be great.

---

Edit: Andreas gave a nice build for parametric $k$.

What about the case that $k$ is a small, fixed number?

If $k=2$, then it's easy: take $\mathcal{P}=\{<1,2,...,n>,<n,n-1,...,1>\}$.

Can we build $O(1)$ sized 3-perfect permutation family? higher fixed $k$?

Answer 1

Here is a sketch on how to do almost what you want, but not quite. It only proves a $k^{k+\operatorname{polylog}(k)}\log n$ bound.

Consider a set of size $m=n\log_2 k$ which we think of as $n$ groups on $\log_2 k$ elements each.

Next construct an $(m,k\log_2 k)$-universal set family $F$ of size $2^{k\log k+\operatorname{polylog}(k)}\log m$ using the method of Naor, Schulman, and Srinivasan. We interprete each set in $F$ as a string on $n$ symbols from $[k]$ with one symbol for each group.

Now we turn each string into a permutation of $[n]$ in the following way:

We first think of the $n$ first positive integers divided in $k$ stacks $T_0$ throgh $T_{k-1}$ where $T_0$ contains the elements $1,...,n/k$ from top to bottom, $T_1$ contains $n/k+1,...,2n/k$, and so on.

We parse each string $s_1s_2...s_n\in F$ into a permutation by considering the symbols one at a time for increasing $j$, and on encountering symbol $s_j$ we pop the stack $T_{s_j}$ from the top and put that number in place $j$ of the permutation.

Since the family $F$ was $(m,k\log_2 k)$-universal, we know that for every ordered set of $k$ of the $n$ groups, there is one string that maps the symbols $0$,$1$,...,$k-1$ to that ordered set. By the construction of the stacks, the elements fetched to the permutations preserve the order required.