4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer, it clearly makes sense. On the other hand, correspondence between distance on the sphere and distance in group actions may not be that straightforward. For example, let us consider simpler example - Hamming distance between sets. For three sets, $A$, $B$ and $C$, minimal pairwise distance, normalized by $n$, would be $2/3$, for example if $|A\cap B| = |A\cap C| = |B\cap C| = 1/3$ and $|A\cap B \cap C = 0|$. However now we may add an empty set $I$, with distance between $I$ and $A$, $B$ or $C$ being also $2/3$. This clearly cannot be achieved in Euclidean metric. $\endgroup$ – Bogdan Chornomaz Sep 9 '16 at 13:44
  • $\begingroup$ In case of sets, it seems that optimal asymptotic (over $n$) distance between $k$ sets is $\lceil \frac{k}{2} \rceil \lfloor \frac{k}{2} \rfloor/\binom{k}{2}$. I wonder to what extent does it comply with your group-action approach? $\endgroup$ – Bogdan Chornomaz Sep 9 '16 at 13:52
  • $\begingroup$ On the other hand, I was kind of expecting that this problem would already be taken to pieces at some handbook. Because the question looks very natural to me. $\endgroup$ – Bogdan Chornomaz Sep 9 '16 at 13:57
  • $\begingroup$ I would be surprised if the difference between Euclidean and Cayley-graph-metric distance were not bounded by a reasonably small constant fraction of each, however I'm not sure where to start to look for this result. I will post a followup question and link to it. $\endgroup$ – benblumsmith Oct 3 '16 at 22:14
  • $\begingroup$ Regarding Hamming distance between sets, the group model is the Coxeter group generated by the reflections in the coordinate hyperplanes $x_i=0$. I would want an optimal distribution of $k$ points on the $n-1$-sphere and then to study how this distribution performs in terms of Hamming distance. If $n$ is large relative to $k$ (in fact as soon as $n\geq k$) one can achieve the minimum distance of $1/2$ (normalized by $\pi$) in the Euclidean case by taking $k$ orthonormal vectors (not optimal but not bad); then the corresponding Hamming distances will also be close to $1/2$ (normalized by $n$). $\endgroup$ – benblumsmith Oct 3 '16 at 22:39
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sure, it is true that the distance $\frac{1}{2}$ can be achieved by random permutations, as well as that the upper bound $\frac{j}{2 j - 1}$ approaches $\frac{1}{2}$ as $k$ grows. On the other hand, at least for $k=3$, one can do better. For example, take three permutations: identical, one that reverses first $\alpha n$, and one that reverses last $\alpha n$ elements. Then optimal $\alpha$ would be $\frac{4+\sqrt{2}}{7}$, giving the pairwise distance about $0.598$, which is substantially larger than $\frac{1}{2}$. $\endgroup$ – Bogdan Chornomaz Sep 16 '16 at 14:16
  • $\begingroup$ Yes for $k=4$ (so also $k=3$) the pairwise distances can all be exactly $\frac23$ in case $n$ is a multiple of $6.$ I revised the answer to make that clearer. I was going for a quick intro before. $\endgroup$ – Aaron Meyerowitz Sep 16 '16 at 22:34
  • $\begingroup$ Thanks, your example has led me to the proof of your first conjecture, which I put below. I think the proof can also be strengthened to show that you can have $c_k$ instead of $O(n)$, for large $n$, and possibly even to show that your second conjecture also holds. $\endgroup$ – Bogdan Chornomaz Sep 17 '16 at 11:55
0
$\begingroup$

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.

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