3
$\begingroup$

Let $S$ and $S'$ be subsets of size $k$ of $\mathfrak{S}_n$.

  1. Are there any necessary or sufficient conditions to determine whether or not $S$ and $S'$ yield isomorphic Cayley graphs?

  2. Assuming we are able to partition the $k$-subsets of $\mathfrak{S}_n$ into equivalence classes, where two sets are equivalent if they yield isomorphic Cayley graphs, is there an algorithm that visits each equivalence class exactly once, generating an arbitrary representative of each class as it goes?

To the best of my knowledge, answers to both questions are known only for transpositions: a set of transpositions generates $\mathfrak{S}_n$ iff its "transposition graph" (vertices = {1, 2, ..., n}, edges = transpositions) is connected; $S$ and $S'$ yield isomorphic Cayley graphs iff their transposition graphs are isomorphic; and therefore, an algorithm for listing all nonquivalent sets would be to generate all graphs on $n$ vertices and $k$ edges, labelling their vertices arbitrarily so as to yield a set of transpositions.

$\endgroup$
  • 3
    $\begingroup$ If two subsets are related by a group automorphism, then the corresponding Cayley graphs are isomorphic. This is sufficient but not necessary. Groups for which this is necessary are called CI-groups and there is a large literature on them. Restricting attention to the subsets of a particular size, the terminology is that a group is $k$-CI if the subsets are related by a group automorphism whenever the Cayley graphs are isomorphic. I don't know the exact status for the symmetric group, but there are others who read this who do (eg verret). $\endgroup$ – Gordon Royle Sep 18 '17 at 11:27
  • 3
    $\begingroup$ Since an arbitrary subset of $S_n$ of size greater than $1$ generates $S_n$ with high probability, the number of generating sets is not much less than the total number of subsets, which is $2^{n!}$. I would guess that in general Cayley graphs of generating sets are isomorphic only if they are conjugate under $S_n$, so the number of isomorphism types of Cayley graphs might be of order $2^{n!}/n!$. If that is correct, then it is not reasonable to expect there to be a useful algorithm that generates one graph from each equivalence class. $\endgroup$ – Derek Holt Sep 18 '17 at 11:32
  • $\begingroup$ Do you mean that Caylay graphs are directed and labelled? If yes, doesn't any isomorphism of Cayley graph induce an automorphism of $\mathfrak S_n$? $\endgroup$ – Ilya Bogdanov Sep 18 '17 at 12:56
  • $\begingroup$ @IlyaBogdanov: not necessarily. In fact, I'm mostly interested in sets closed under inverses which yield left-invariant metrics, so most of the time the Cayley graphs I'll obtain will be undirected. $\endgroup$ – Anthony Labarre Sep 18 '17 at 13:27
  • 1
    $\begingroup$ There are non-isomorphic generating sets with isomorphic Cayley graphs. E.g., all sets of the form $\mathfrak S_n\setminus\{\sigma\}$ where $\sigma$ is an involution provide isomorphic Cayley graphs; yjr same holds if we remove all posers of a permutation of a fixed order. $\endgroup$ – Ilya Bogdanov Sep 18 '17 at 17:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.