Skip to main content
MathOverflow

Return to Question

added 126 characters in body
Source Link
Bogdan Chornomaz
Bogdan Chornomaz
  • 91
  • 5

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

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

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

added tags symmetric-group (since the question is about permutations) and coxeter-groups (since it involves a distance equivalent to to the coxeter group word length metric)
Link
edit approved Sep 6, 2016 at 15:42
benblumsmith
edit approved Sep 6, 2016 at 15:42
benblumsmith
  • 2.9k
  • 18
  • 26
Source Link
Bogdan Chornomaz
Bogdan Chornomaz
  • 91
  • 5

Maximal pairwise distance between $k$ permutations

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