4
$\begingroup$

This is a problem I asked on https://math.stackexchange.com/questions/647382/union-of-permutations. Feel free to close it if you think it below research level.

Having $k$ different permutations, $\pi_{1},\dots,\pi_{k}: \{1\ \ldots\ n\}\rightarrow \{1\ \ldots\ n\}$, the union of permutations is defined as follows:

$$\forall i{\in}[n],\ U_i=\{{\pi}_1(i),{\pi}_2(i),\dots,{\pi}_k(i)\}$$

Note that in $U_i$ there may be repetitions, so $|U_i|{\leq}k$, let $s=\sum_i^n|U_i|$, so I want to ask, what is the minimum $\sigma(n\ k)$ of all $s$ as above for any $k$ permutations?

For example, if we let $n=4,k=3$, we have three permutations \begin{equation}\pi_1=1234,\pi_2=2134,\pi_3=3421\end{equation} coded in the obvious way, then \begin{equation}U_1=\{1,2,3\},U_2=\{2,1,4\},U_3=\{3,2\},U_4=\{4,1\}\end{equation} so $s=3+3+2+2=10$. But we have a better choice: \begin{equation} \pi_1=1234,\pi_2=2134,\pi_3=1324 \end{equation} here \begin{equation} U_1=\{1,2\},U_2=\{2,1,3\},U_3=\{3,2\},U_4=\{4\} \end{equation}, $s=2+3+2+1=8$.

Intuitively, the more the different permutations share common parts, the less $s$ will be, so if we let $k=i!$, then for permutations in the form $\pi=(\pi^{*})(i+1)(i+2){\dots}n$ where $\pi^{*}$ is any permutation of $1,2,\dots,i$, namely the $k$ different permutations differ only on the first $i$ elements, then $s$ may be minimum, and $s=i^2-i+n$. Take $n=6, k=6$ for example, the best choices of 6 different permutations may be: \begin{equation} \pi_1=123456, \pi_2=132456, \pi_3=213456, \pi_4=231456, \pi_5=312456, \pi_6=321456 \end{equation} and the best $s=3+3+3+1+1+1=12$. But this is a simple intuition; does anyone know what is the exact answer to this question?

$\endgroup$
2
  • $\begingroup$ Just a reformulation which may look more familiar to someone. Given that the permanent of a 0-1 matrix $A$ is at least $k$, find the minimal sum of its elements. $\endgroup$ Jan 28, 2014 at 4:21
  • 1
    $\begingroup$ For $n=6$, you may achieve more permutations keeping $s=12$. Set $U_1=U_2=\{1,2\}$, $U_3=U_4=\{3,4\}$, $U_5=U_6=\{5,6\}$. This pattern clearly fits for 8 permutations. So the optimal configuration should be a different one. (To make it more evident, compare $5!=120$ permutations obtained by permutations of the first 5 numbers with $2^7=128$ permutations obtained by switchings of 7 pairs of numbers.) $\endgroup$ Jan 28, 2014 at 4:28

2 Answers 2

1
$\begingroup$

$\def\perm{\mathop{\rm perm}}$This is a partial answer for the case when $n$ is large enough. In particular, we show that for $k=2^\ell$ and $n\geq 2\ell$ we have $s\geq n+2\ell$, supported by the model $U_{2i}=U_{2i-1}=\{2i-1,2i\}$, $i=1,\dots,\ell$.

For convenience, let us consider the permanent reformulation of the problem. Let us show that for every $s=n+\delta$, if the sum of elements of a 0-1 matrix $A$ is $s$ then $\perm A\leq 2^{\delta/2}$. The base case $\delta\leq 1$ is clear.

Take the row or column of $A$ containing the least number $t$ of 1's (WLOG this is the first row). If $t=0$, the statement is clear. So assume that $t\geq 1$. Then $$ \perm A=\sum_{i=1}^t \perm A_i, $$ where $A_i$ is obtained from $A$ by deletion of the first row and the column with $i$th one. Let $s_i=(n-1)+\delta_i$ be the sum of elemtents of $A_i$; then $\delta_i\leq \delta-2t+2$, because the deleted column had at least $t$ ones. Thus $$ \perm A\leq t2^{(\delta-2t+2)/2}. $$ Notice that $t2^{-t}\leq 1/2$ for positive integer $t$; so $\perm A\leq 2^{\delta/2}$ as required.

Remarks. Notice that if $t\geq 3$ on some step, then the estimate makes less by a factor of at most $3/4$. On the other hand, if in some deleted column we have more than $t$ ones (for $t=1$ or $t=2$), then the estimate also decreases by at most $\displaystyle\frac{\sqrt2+1}2<\frac34$. In particular, one may see that this estimate can be tighten for all odd $\delta$.

Right now I do not see how to extend this for larger values of $k$; but it may happen that the optimal example still consists of several blocks on the diagonal of almost the same size.

$\endgroup$
0
$\begingroup$

You could look for a sequence of permutations, that are adjacent in the Steinhaus-Johnson-Trotter sequence of permutations
http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithmsequence
for minimizing $s$, or, for those adjacent in the DeBruijn sequence
http://en.wikipedia.org/wiki/De_Bruijn_sequence
for more general questions regarding $s$

$\endgroup$
2
  • $\begingroup$ Any proof showing $k$ permutations in Steinhaus-Johnson-Trotter does minimize $s$, or just intuitively because they differ only a little? $\endgroup$
    – Yu Song
    Jan 28, 2014 at 7:33
  • $\begingroup$ just intuitively; would have to be checked whether Steinhaus-Johnson-Trotter yields smaller $s$ than lexicographic order of permutations. $\endgroup$ Jan 28, 2014 at 7:45

Your Answer

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

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