# Weights on cyclic orderings

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.

• 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. – kcrisman Oct 27 '15 at 19:03
• 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. – Dima Pasechnik Oct 27 '15 at 22:10

## 1 Answer

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.