Skip to main content
2 of 2
deleted 1 character in body

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.