Cyclic Permutations Explained in Combinatorics

co.combinatoricsgraph theorypermutationssymmetric-groups

This question is not about elements of $S_n$ that consist of a single $n$-cycle, though naturally it's related.

Instead, consider permutations modulo the action of $(123\ldots n)$. That is, we want ABCD to be the same as BCDA and CDAB and DABC. (It's optional whether this also is the same as DCBA, but for now let's say it's not.) I am primarily interested in the graph that these generate, sort of like the Cayley graph for $S_n$ with generators $(12),(23),\ldots (n-1 n),(n1)$, but with vertices and edges identified. (I don't think this is a Cayley graph of a quotient of $S_n$; I don't even think this set is identifiable with a group since that subgroup isn't normal, if I recall correctly.)

What are these things called, and are there references to them in the literature? (Say to their symmetry groups, rep. theory, or whatever else.) I can't imagine there aren't, but because 'cyclic permutations' nearly always means something else, it's frustrating to look for this. I found pages of MathSciNet references to those terms, and none were about this. Not surprisingly! But presumably combinatorics experts have studied them – not just counted them, though Polya enumeration immediately comes to mind.

Edit: For a concrete example, imagine people around a dinner table, where you don't care which chair you sit in, you just care what the arrangement is. Maybe it's been thought of that way before?

Edit: Well, I have to say that Tilman and Mark Sapir both have been very helpful, but I guess Tilman answered the actual question.

Very oddly, I can only find ONE paper on MathSciNet that actually deals with the object I am interested in directly – Woodall's "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture" proves some basic facts. Nearly every reference to such things is about using cyclic orders without considering all of them (in graph theory or queueing theory), is using them to create ribbon graphs, or is about extending partial cyclic orders to complete cyclic orders.

Best Answer

They're called cyclic orders or cyclic orderings. Since they don't form a group, as you noticed, there's no representation theory. They play a role in the study of moduli spaces via ribbon graphs, for example. A ribbon graph is a graph with a cyclic ordering of the edges incident to every vertex. If you look for "cyclic order" and "ribbon graph", you'll probably find some sources.

Related Question