How can k permutations on n-set be arranged to maximize minimal pairwise Kendall tau distance (i.e. number of discordant pairs) between them?
For two permutations this is obviously when the second permutation is the reverse of the first one, with distance $n(n-1)/2$, but what about larger $k$?
Update: The main question is the asymptotic of normalized (by the factor $n(n-1)/2$) distance when $n \rightarrow \infty$.
This is only a partial answer.
The problem is a discrete version of equidistributing $k$ points in an $n-2$-sphere. We see this as follows:
The pairwise Kendall tau distance between permutations $\pi$ and $\rho$ is the number of inversions of $\pi\rho^{-1}$, since $\pi(i)>\pi(j)$ while $\rho(i)<\rho(j)$ if and only if $\pi\rho^{-1}(i')>\pi\rho^{-1}(j')$ while $i'<j'$, by letting $i'=\rho(i),j'=\rho(j)$, and similarly for the reverse inequalities.
This in turn is equivalent to the distance in the graph metric for the Cayley graph of $S_n$ with transpositions of adjacent letters as generators.
Since $S_n$ is a Coxeter group of rank $n-1$ with these generators as Coxeter generators, this graph is the dual of the Coxeter complex, and therefore embeds regularly in an $n-2$-sphere. (One can think of this sphere as being the intersection of the unit sphere in $\mathbb{R}^n$ with the hyperplane $\sum x_i=0$. The Coxeter complex is the simplicial complex structure on this sphere given by intersecting it with all the hyperplanes $x_i=x_j$. The vertices of the Cayley graph could be taken to be the barycenters of the top-dimensional simplices, and the edges would link any two of these that are adjacent across one of the $x_i=x_j$ hyperplanes.) The graph distance is reasonably well approximated by the Riemannian distance in the sphere.
Addendum:
Actually I think this idea can be used to translate an optimal distribution of $k$ points on an $n-2$-sphere to a close-to-optimal distribution of permutations. (Not sure how close exactly, because of uncertainty about the relation between the Cayley graph distance and the Riemannian distance, but I'd be surprised if it wasn't quite close.)
For this I think it's easiest to forget the Cayley graph and think about the Coxeter complex directly. Permutations biject with chambers of the Coxeter complex, and the distance is given by the minimum number of walls (hyperplanes $x_i=x_j$) crossed to get from one chamber to another. Just take an optimal distribution of $k$ points and isometrically embed it in the Coxeter complex so that each point is in a chamber (if any points hit walls, perturb the embedding slightly), and then just look at which chambers the points are in! If we use the description of the Coxeter complex given above, this is easy, because points of $\mathbb{R}^n$ minus all the hyperplanes $x_i=x_j$ have distinct coordinates, and are thus canonically associated to permutations by looking at the order of the coordinates.
Example:
Take $n=4, k=4$. Four points are equidistributed on a $n-2 = 2$-sphere as the vertices of a tetrahedron. I would like to embed such an arrangement in a sphere lying in the trace-zero hyperplane $\sum x_i = 0$ in $\mathbb{R}^{n=4}$. I could take the vertices as $$(3,-1,-1,-1),(-1,3,-1,-1),(-1,-1,3,-1),(-1,-1,-1,3).$$ (There is no need to constrain them to be on the unit sphere because we can tell what chamber they end up in just from the order of the coordinates.)
Now the issue with these vertices is that they have lots of collisions between the coordinates, so they do not lie in the interiors of the Coxeter chambers. So I want to perturb the whole thing slightly with a small orthogonal transformation that preserves the trace-zero hyperplane. Doing this by hand: switching to column notation for $\mathbb{R}^4$, how about the transformation
$$ T = \begin{pmatrix}\cos \epsilon & -\sin \epsilon & & \\ \sin \epsilon & \cos \epsilon & & \\ & &1& \\ & & &1\end{pmatrix}$$
except with respect to the basis
$$B = \begin{pmatrix}1/2\\-1/2\\-1/2\\1/2\end{pmatrix},\; \begin{pmatrix}1/2\\-1/2\\1/2\\-1/2\end{pmatrix},\; \begin{pmatrix}1/2\\1/2\\-1/2\\-1/2\end{pmatrix},\; \begin{pmatrix}1/2\\1/2\\1/2\\1/2\end{pmatrix}$$
in order to preserve the trace-zero subspace. If my calculation is right we have $T' = BTB^{-1} = \frac{1}{2}\begin{pmatrix}\cos \epsilon + 1& -\cos \epsilon + 1 & -\sin \epsilon & \sin\epsilon \\ -\cos\epsilon + 1& \cos \epsilon + 1& \sin\epsilon & -\sin\epsilon\\ \sin\epsilon & -\sin \epsilon & \cos\epsilon + 1 & -\cos\epsilon + 1\\ -\sin\epsilon & \sin\epsilon & -\cos\epsilon + 1 & \cos\epsilon + 1\end{pmatrix}$
I have to multiply this matrix by the four points of the tetrahedron and observe the order of the coordinates. Since I am doing this by hand and thus looking for shortcuts, I observe that the four points each have the form $(-1,-1,-1,-1)^T + 4e_i$ for $i=1,2,3,4$, and $T'(-1,-1,-1,-1)^T = (-2,-2,-2,-2)^T$, thus the order of the coordinates of the $i$th point will simply be given by $T'e_i$, i.e. the $i$th column of $T'$. Since $\epsilon$ is supposed to be small positive, we have $-\sin\epsilon<0<1-\cos \epsilon < \sin \epsilon < 1 < 1 + \cos\epsilon$, and thus the four permutations (reading from greatest to least, because why not) are
1324, 3142, 4213, 2431
The Kendall tau distances are all at least 3. I believe this is optimal.
Consider the average pairwise distance and minimum pairwise distance for a set of $k$ permutations from $S_n.$ Let the maximum values among all choices of $k$ permutations be $\alpha_{n,k}=a_{n,k}\binom{n}2$ and $\mu_{n,k}=m_{n,k}\binom{n}2$ respectively. Then $$m_{n,k} \le a_{n,k} \le \frac{j}{2j-1}$$ for $k=2j-1$ or $k=2j.$
So for $k$ not too small this upper bound just a little more than $1/2.$ The expected minimum value for random choices should converge to $1/2$ as $n$ increases for $k$ fixed (and hence also for $k$ growing slowly enough relative to $n.$)
I'd conjecture that $$\mu_{n,k} = (\frac{j}{2j-1})\binom{n}{2} -O(n)$$ Perhaps even $$\mu_{n,k}=\lfloor\frac{j}{2j-1}\binom{n}{2}\rfloor$$ for $n$ large enough with respect to $k.$
For $k=2$ we have $\frac{j}{2j-1}=1$ and, as noted, $\mu_{n,1}=1$.
For $k=3,4$ we have $\frac{j}{2j-1}=\frac{2}{3}.$ The triple $1234,2431,4231$ have pairwise distances $4$ but one can't achieve this for four permutations. The quadruple $1234,4321,1432,3214$ has average distance $\frac{22}{6}$ and minimum $3.$ However for $n=6$ the quadruple $123456, 16\overline{5432}, \overline{61}54\overline{23},\overline{6512}43$ (ignore the overbars for a moment) have pairwise distances $10=\frac23\binom62.$
For $k=4$ and $n=6m$ consider the example above where $j$ is replaced by $(j-1)m+1,(j-1)m+2,\cdots,jm$ and $\overline{\,j\,}$ by the reverse of that. Then the pairwise distances are all $\frac23\binom{n}2.$
Given $k=2j$ permutations from $S_n,$ the greatest total sum of distances (if possible) will occur if for each pair of positions $j$ have an increase and the other $j$ a decrease. If this happens exactly, then the average distance is $$\frac{\binom{n}2j^2}{\binom{k}2}=\frac{\binom{n}2j^2}{\binom{2j}2}=\frac{\binom{n}2j}{2j-1}.$$
For $k=2j-1$ the greatest total sum will occur if in each pair of positions $j-1$ or $j$ have an increase. If this happens exactly, then the average distance is $$\frac{\binom{n}2j(j-1)}{\binom{k}2}=\frac{\binom{n}2j(j-1)}{\binom{2j-1}2}=\frac{\binom{n}2j}{2j-1}.$$
The expected distance between two permutations is the same as the expected number of inversions in a random permutation. This is easily seem to be ${\binom{n}{2}}/{2}.$ This follows from the deeper observation that the distribution of distances from a fixed permutation is symmetric about this central value.
In fact, according to this article, the distribution of distances converges to a normal distribution. It seems a small step from this to get that for fixed $k$ and $\epsilon \gt 0$ and with a uniform random selection of $k$ permutations from $S_n$, the probability that all $\binom{k}{2}$ pairwise distances are in the range $((1/2-\epsilon)\binom{n}2,(1/2+\epsilon)\binom{n}2)$ goes to $1$ as $n$ increases.
Thanks to $k=3,4$ construction by Aaron Meyerowitz above, I can now give an answer, for an asymptotic case, confirming his first hypothesis (I use $d$ instead of $\mu$ to denote distance)
$$d_{n,k} = (\frac{j}{2j-1})\binom{n}{2} -O(n).$$
We will consider normalized distances taking values on $[0,1]$. For the proof we have to use several facts.
First, Kendall tau distance between permutations equals to Huffman distance (the size of symmetric difference) between their sets of discordant pairs.
Second, similar task for sets admits an exact bound $\beta_{k} = \lceil \frac{k}{2} \rceil \lfloor \frac{k}{2} \rfloor/\binom{k}{2}$, or, as Aaron had put it, $\beta_{k} = \frac{j}{2j-1}$ for $k=2j$ or $k=2j-1$. Sets attaining this bound can be easily constructed in the following way: let us split $n$ into $\binom{k}{j}$ (almost) equal parts $A_S$, indexed by the subsets of $k$ of size $j$. Now, take $$A_i = \bigcup\{A_S~|~i\in S\}.$$
Third, as an approximation of the finite case, we may take a measurable ground set $A$ with $\mu (A)=1.$ Using similar construction, we can use the above argument to construct $A_i, i=1\dots k$, with pairwise distance equal to $\beta_k$, where $d(A_i, A_j) = \mu(A_i\oplus A_j)$.
Now, we will seek the answer among permutations $P_X$, $X\subseteq n$, such that $D(P_X) = \{(i,j)~|~i\in X, j>i\}$, where $D(P)$ is a set of discordant pairs of $P$ (for each $X$, such permutation exists). One can easily see that
$$d(P_X, P_Y) = \frac{2}{n}\sum_{x\in X\oplus Y }\ \frac{n-x}{n-1}. $$
In limit case we than want to maximize pairwise distance between subsets of $[0, 1]$ with density $\rho(x) = 2*(1-x)$. This is easily achieved using argument above. Again, it is quite clear that for large $n$ this limit case can be approximated with arbitrary precision.
