MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, Everyone:

I would appreciate some references for the version of Reidemeister-Schreier that is used to find the stabilizer of a point under a group action. The only refs. I have found are about Schreier-Sims method, but I have not been able to find anything on it.

The version of R-S I know of allows us to find a presentation of a subgroup H of a group G, by using transversals, etc.

I think there is a connection between the two, but I am not sure.

Thanks in Advance.

Sorry, I forgot to ask something important: I would like to know how the following process --the adaptation of R-S to group actions ( or maybe a version of Cayley graphs) produces a set of generators for the stabilizer of a fixed element sk , under a group action:

We start with a group action HxS-->S (could also be a left action), and we are given the (finite) set {$h_1$,..,$h_n$} of generators for H; S is a finite set. We then define a graph G by:

1)The vertices are the elements sj of S

2)We join $s_i$ with $s_k$ with an edge labeled $h_j$ , if $h_j$.$s_i$=$s_k$ , i.e., if the action of $h_j$ on $s_i$ results in sk.

3) We construct a spanning-tree T for G, rooted at $s_k$ (the element of S being stabilized); I think it is clear that G is connected --|n|-connected, actually, where n is the size of the generating set for H (tho we mayhave loops) , to guarantee the existence of a spanning- tree.

Claim: the edges in G-T generate the stabilizer Stb{{$s_k$})of $s_k$ under this action.

Anyone have a suggestion for showing this?

I don't remember the place where I read this, but I remember some related results:

The background/context is a generalization of the fact that , given a group H and any subgroup

H' of H , there is an action by H for which H' is the stabilizer. Specifically, this

action is the "standard" action of H on H/H' (standard group quotient); we just define, for

any h1H' on H/H' and h in H:

h.(h1H' ) --> (h.h1)H'

Then H' is the stabilizer of the coset eH'=H' .

I think this is also related to the method for finding the fundamental group of a rooted

connected graph G: we find a spanning-tree T. Then each edge e=(gi,gj) in G-T defines a non-

trivial element of $Pi_1$(G): we start at , say, $g_i$ (which is in T, since T spans) , then we

find the (unique; any two paths would form a loop in T) path $P_i$ in T from $g_i$ to the root g,

and from g we find the unique path $P_j$ to $g_j$; the other vertex in e. Then the composition

$P_i$$P_j$e forms a non-trivial loop in G. It is just a little more work to show that these

edges freely generate the fundamental group.

These are the results that were related to the issue of the stabilizer.

Thanks for any Suggestions, Refs.

share|cite|improve this question
The first hit on Google for "Reidemeister-Schreier" is and might already be answering your question. – Tom De Medts May 11 '11 at 7:50
Yes, it deals with standard R-S, which finds a prsentation of a group from that of a subgroup, which is difficult to apply to this case; I am working with the mappingclasss group and the subgroup SP_2, the Spin-mapping class group (as the stabilizer of the Rokhlin form), which does not lend itself well to the method described there. Same for the Wiki page. – Larry May 11 '11 at 9:12
I suspect that the Schreier-Sims method is not relevant to what you want. "Schreier-Sims" usually refers to the algorithm for finding the order of the finite group $G$ generated by a set of permutations on a finite set. To do this, it uses a theorem of Schreier for finding generators of the the stabilizer of a point in $G$. – Derek Holt May 11 '11 at 10:46
@Larry : Unless you are only interested in very low-genus cases (say, $g$ at most 2 or 3), I suspect that you won't be able to apply any version of the RS method to get a presentation of the spin mapping class group. The index is just too big. Even if you manage to get a computer to do it for you, the presentation will be enormous and not very enlightening. – Andy Putman May 11 '11 at 13:59
@Larry : The Torelli group is nontrivial even in genus $2$. In genus $2$, the spin mapping class group has index 72 if you are considering even spin structures and index 120 if you are considering odd spin structures. This is small enough that a computer will be able to run the RS algorithm and give you an answer; however, I suspect that the resulting presentation will be far too complicated to be of much use. – Andy Putman May 11 '11 at 15:04
up vote 3 down vote accepted

This is an answer to the OP's second question. Let $H$ be a group acting, say on the right, on a set $S$. Suppose that $H$ is generated by $X$, and let $G$ be the graph with vertex set $S$ and edges of the form $(s,sx)$, where $s \in S$ and $x \in X$. Then $G$ is connected if and only if $H$ acts transitively on $H$: a path from $s$ to $s'$ yields a sequence $x_1^{\epsilon_1}, \dots, x_n^{\epsilon_n}$ and the product of these represents an element $h$ such that $sh = s'$.

Fix $s \in S$. Suppose $P$ is a collection of closed paths in $G$ based at $s$ such that every closed path based at $s$ is expressible as the concatenation of finitely many paths in $P$. To each path $p \in P$ you can associate a word $w_p$ over $X$ and, hence, a element of the group $H$. We have that $H_s = gp\langle \ w_p : p \in P \ \rangle$: every such word stabilizes $s$, and every element of the stabilizer, when expressed as a word in $X$, defines a closed path at $s$; the latter closed path is a concatenation of the subpaths which define closed paths at $s$ and so the word is expressible as a product of the $w_p$'s and their inverses.

To find such a generating set for $H_s$, choose a spanning tree $T$ in $G$. For each edge $e$ in $G-T$, let $p_e$ be the unique reduced path in $T$ from $p$ to the initial vertex of $e$ followed by $e$ followed by the unique reduced path in $T$ from the terminal vertex of $e$ to $s$. Each such path $p_e$ defines a word over $X$ and these words generate $H_s$ as in the above proof.

If $S$ is the set of right cosets of a subgroup $H' < H$, then $T$ is essentially a Schreier transversal and the elements defined by the paths $p_e$ are the generators which are commonly denoted $\gamma(t,x) = tx\overline{tx}^{-1}$, where $F$ is free with basis $X$, $F'$ is the preimage of $H'$ under a map $F \to H$ which realizes $X$ as a generating set for $H$, $T$ is a Schreier transversal for $F' < F$, and $\bar{w}F' = wF'$ is the unique coset representative $\overline{w} \in T$ for $w$.

There is a detailed treatment in the textbook by Lyndon and Schupp.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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