5
$\begingroup$

Are there standard or known weights/metrics on cyclic orders?

Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a rotation. For example, the ways that 4 people can sit at a circular table, where you ignore rotation of the table.

So the following 4 rankings of a 4-item set should be considered the same:

[2,1,4,3]
[1,4,3,2]
[4,3,2,1]
[3,2,1,4]

You can think of this as arranging the 4 items on a circular list, with no particular top, but a definite direction.

I would like to compare different cyclic orderings in a meaningful way. I have learned that there are many well-known ways of assigning distance or weight to non-cyclic orderings (a.k.a. permutations!). For example:

  • Kendall $\tau$
  • Transposition distance (Cayley)
  • Ulam metric
  • Hamming weight
  • $\ell_1$ norm

But these give different weights to permutations which correspond to the same cyclic ordering.


A first simple idea is the following: given a permutation $a$, count the number of $i$ such that $a(i+1) \neq a(i) +1$, where $0 \leq i \leq n$ and index addition is performed modulo $n$.

A natural variation on this idea would sum $|a(i+1) - (a(i)+1)|$.

I haven't thought about either of these too carefully yet. Do they appear in the literature somewhere? Some nontrivial internet searching hasn't turned anything up.

$\endgroup$
2
  • 2
    $\begingroup$ See also mathoverflow.net/questions/58782/… - Woodall's "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture" is the most interesting paper on this, from my perspective, because it actually constructs the graph of these things under a certain definition of this distance (one I like best). I do not know of any theoretical discussion of the issue you mention, though I'm glad to hear of Dima's computational one - and if it was actually more theoretical in that paper than I though, he'll let me know :) which I will find useful. $\endgroup$
    – kcrisman
    Oct 27, 2015 at 19:03
  • 1
    $\begingroup$ we (and Woodall, and Kleitman) define the graph on these $(n-1)!$ elements of $S_n$, so that two such elements are adjacent if one needs to swap two adjacent positions to get one from the other. $\endgroup$ Oct 27, 2015 at 22:10

1 Answer 1

2
$\begingroup$

cyclic permutations, and a need to define distances on them, pops up in literature on graph crossing numbers, e.g. we used it in http://arxiv.org/abs/math/0404142

It probably goes back all the way to at least

D.J. Kleitman, The crossing number of $K_5$. J. Combinatorial Theory 9 (1970), 315–323.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.