<p>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.</p>

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

<p>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 <a href="http://dl.acm.org/citation.cfm?id=796315" rel="nofollow">Naor, Schulman, and Srinivasan</a>. We interprete each set in $F$ as a string on $n$ symbols from $[k]$ with one symbol for each group.</p>

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-01-23T10:10:43.647Z
2014-01-23T12:13:29.763Z
2014-01-23T12:13:29.763Z
Andreas Björklund
<p>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=&lt;x_1,x_2,...,x_k&gt;, (x_i \in [n])$, there exists a permutation $P \in\mathcal{P}, $ such that $P(x_1)&lt;P(x_2)&lt;...&lt;P(x_k)$.</p>

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

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

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

<p>$(1-\frac{1}{k!})^r\cdot$$ n\choose k$$\cdot k!&lt;(1-\frac{1}{k!})^r\cdot n^k &lt; n^k\cdot e^{-r/k!}$</p>

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

<p>The question is:</p>

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

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

<hr>

<p><strong>Edit:</strong> Andreas gave a nice build for parametric $k$.</p>

<p><strong>What about the case that $k$ is a small, fixed number?</strong></p>

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

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

CC BY-SA 3.0
2014-01-23T00:56:04.497Z
I have a construction in $O_k(\log^{O_k(1)} n)$ – is that good enough?
Yuval Filmus
CC BY-SA 3.0
2014-01-23T01:09:19.513Z
This is related to covering designs. See http://arxiv.org/abs/1203.5433 for the particular case $k = n-1$ of your problem.
Yuval Filmus
CC BY-SA 3.0
2014-03-27T13:57:19.963Z
you might be able to get some ideas from the paper "Splitters and near-optimal derandomization" by Moni Naor, Leonard J. Schulman and Aravind Srinivasan,
greg
<ds.algorithms><co.combinatorics><extremal-combinatorics>
Constructing a k-perfect permutations family
R B
# Constructing a k-perfect permutations family

(Asked by: username_0 on 2014-01-23)

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\_i \in [n])$, there exists a permutation $P \in\mathcal{P}, $ such that $P(x\_1)

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 $$ 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>,\}$.

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

**Tags:** ds.algorithms, co.combinatorics, extremal-combinatorics
> **Comments:**
> **username_1**: I have a construction in $O_k(\log^{O_k(1)} n)$ – is that good enough?  
> **username_1**: This is related to covering designs. See http://arxiv.org/abs/1203.5433 for the particular case $k = n-1$ of your problem.  
> **username_2**: you might be able to get some ideas from the paper "Splitters and near-optimal derandomization" by Moni Naor, Leonard J. Schulman and Aravind Srinivasan,  

---

## 1 answers

### Answer by username_3 on 2014-01-23. Score: 6 | Accepted answer

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](http://dl.acm.org/citation.cfm?id=796315). 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.


---

