Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a problem I asked on http://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?

share|improve this question
    
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. –  Ilya Bogdanov Jan 28 at 4:21
1  
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.) –  Ilya Bogdanov Jan 28 at 4:28
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
add comment

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$

share|improve this answer
    
Any proof showing $k$ permutations in Steinhaus-Johnson-Trotter does minimize $s$, or just intuitively because they differ only a little? –  Yu Song Jan 28 at 7:33
    
just intuitively; would have to be checked whether Steinhaus-Johnson-Trotter yields smaller $s$ than lexicographic order of permutations. –  Manfred Weis Jan 28 at 7:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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