6
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ I have a construction in $O_k(\log^{O_k(1)} n)$ – is that good enough? $\endgroup$ – Yuval Filmus Jan 23 '14 at 0:56
  • 1
    $\begingroup$ This is related to covering designs. See arxiv.org/abs/1203.5433 for the particular case $k = n-1$ of your problem. $\endgroup$ – Yuval Filmus Jan 23 '14 at 1:09
  • $\begingroup$ 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, $\endgroup$ – mobius dumpling Mar 27 '14 at 13:57
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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