Union of Permutations

Question

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?

Answer 1

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

Answer 2

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$