12
$\begingroup$

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.

$\endgroup$

4 Answers 4

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ah, but I care about the automorphism group of the graph of such things. So I still get representations :) Thanks! $\endgroup$
    – kcrisman
    Mar 18, 2011 at 13:20
12
$\begingroup$

I think what you get is the Schreier coset graph for the subgroup generated by the $n$-cycle.

$\endgroup$
2
  • $\begingroup$ Hmm, that is helpful. Is there any information out there about this particular Schreier graph? It would surprise me if these cycles hadn't been discussed somewhere. $\endgroup$
    – kcrisman
    Mar 18, 2011 at 0:31
  • $\begingroup$ There is a reference to Higman's paper in Wiki. It is about using Schreier graphs for alternating groups. I know that Schreier graphs are used often (but not always) when the subgroup is maximal. There are very nice applications of Schreier graphs in the case of infinite groups. That's about all I know. As for your particular graph - I have not seen it before. $\endgroup$
    – user6976
    Mar 18, 2011 at 1:31
2
$\begingroup$

An elementary way to describe the moduli spaces alluded in the reply of Tilman is as follows: Glue the sides of two oriented polygons $P,P'$ with $n$ sides, counterclockwise labeled from 1 to $n$ by a permutation $\sigma$ by identifying side $i$ of $P$ with side $\sigma(i)$ of $P'$ in the unique orientation-preserving way. The result is a compact surface (corresponding to a Riemann surface) $\Sigma$ depending only on the class of $\sigma$ modulo the left and right action of $(1,2,\dots,n)$. The ribbon graph alluded by Tilman is essentially a small neighbourhood of the boundary of $P$ (or $P'$) in $\Sigma$. In other terms, one obtains in this way exactly all ribbon graphs coming from graphs $\Gamma$ having $n$ edges in a compact surfaces $\Sigma$ such that $\Sigma\setminus \Gamma$ consists of two topological discs containing both $\Gamma$ in their boundary.

One way of obtaining such graphs is by so-called "joins", a special type of skew-configurations of lines in $\mathbb R^3$ (a skew-configuration is an isotopy class of finitely many lines with no coplanar pairs of lines), first studied by Viro and collaborators. (This is in fact not quite correct, "joins" need two more types of moves in order to get things up to isotopy, but most joins are "without non-trivial blocks" and correspond thus morally to such classes (this is also not quite correct: one has also to consider the action of the orientation reverting involution $(1,n)(2,n-2)\cdots$)).

$\endgroup$
2
$\begingroup$

Here is one interpretation of this set in terms of Hochschild homology. Let $A$ be the group algebra of $\mathbb{Z}/n\mathbb Z$, and let $B$ be the group algebra of $S_n$ (say over $\mathbb C$ for simplicity). There is a map $A \to B$ taking the generator to the $n$-cycle $(1 2 \cdots n)$, and this makes $B$ an $A$-bimodule. Then the set you define is a basis for the Hochschild homology $HH_0(A, B)$. (Of course, this isn't combinatorial, so I don't know if this is useful for your purposes.)

http://en.wikipedia.org/wiki/Hochschild_homology

$\endgroup$
3
  • $\begingroup$ Very interesting, thanks! Do you have a reference for that specific computation? Everybody seems to want to just talk about Kähler differentials and HH(A,A). Yes, I am lazy and haven't computed an actual concrete homology group in years, though this seems pretty plausible... anyway, it's possible it would give insight into the specific combinatorics I'm interested in. $\endgroup$
    – kcrisman
    Feb 19, 2014 at 20:54
  • 1
    $\begingroup$ I agree, people often focus on the case $M = A$. I think this computation can be done directly from the definition - the $0$ homology is the degree 0 piece mod the image of $d_0$, and $d_0(m\otimes a) = ma - am$. So in the quotient we have $\sigma a = a \sigma$, where $\sigma \in S_n$ and $a$ is the generator of the cyclic group. $\endgroup$ Feb 19, 2014 at 23:56
  • $\begingroup$ Yes, this makes perfect sense, thanks! $\endgroup$
    – kcrisman
    Feb 20, 2014 at 18:28

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.