# induced group actions in GAP

Suppose $G$ is a permutation group acting on some set (for example, $G$ could be the automorphism group of a graph, acting on its vertices). Suppose $G$ also acts on some collection $\Sigma$ of subsets of $\Omega$ (for example, $\Sigma$ could be the set of all maximum cliques of the graph - these objects are also permuted among themselves by each $g \in G$). How do I obtain this induced action or induced permutation representation in GAP? Given $G, \Omega$ and a collection $\Sigma$ of subsets of $\Omega$, I want to find the image $\mu(G)$ of the homomorphism $G \rightarrow Sym(\Sigma)$.

Consider the concrete example where $G$ is the dihedral group of order 12 acting on the vertices of a 6-cycle graph, and $\Sigma$ is a block system, represented in GAP in the form $[ [1,4],[2,5],[3,6]]$. I am looking then for a permutation group that is a subgroup of $Sym(\{1,2,3\})$. Here's what I did in GAP:

gap> G:=DihedralGroup(IsPermGroup,12);
Group([ (1,2,3,4,5,6), (2,6)(3,5) ])
gap> bs:=Orbit(G, [1,4], OnSets);
[ [ 1, 4 ], [ 2, 5 ], [ 3, 6 ] ]
gap> ker:=Stabilizer(G, bs[1], OnSets);
Group([ (2,6)(3,5), (1,4)(2,5)(3,6) ])
gap> ker:=Stabilizer(ker, bs[2], OnSets);
Group([ (1,4)(2,5)(3,6) ])
gap> ker:=Stabilizer(ker, bs[3], OnSets);
Group([ (1,4)(2,5)(3,6) ])
gap> muG:=FactorGroup(G,ker);
Group([ f1, f2 ])
gap> List(muG);
[ <identity> of ..., f2, f2^2, f1, f1*f2, f1*f2^2 ]
gap>


More generally, I tried the following in GAP. Let $\Sigma = \{\Delta_1,\ldots,\Delta_r\}$. GAP has a function to find the set of elements in $G$ that fixes a particular subset $\Delta_1 \in \Sigma$ setwise (it is the command $Stabilizer(G,\Delta_1,OnSets)$). So this function could be used repeatedly to obtain the set $K$ of elements in $G$ that fixes each $\Delta_i$ setwise. This set $K$ is the kernel of the action $\mu: G \rightarrow Sym(\Sigma)$. We can then use the $Factorgroup(G,K)$ command to get the permutation image $\mu(G)$, up to isomorphism. The problem is that when I did this, in general the domain of objects for the factor group $\mu(G)$ was not $\Sigma$.

I guess there must be some way to create a permutation group whose domain is the new set $\Sigma$. Any help would be appreciated.

FactorGroup will only give you some representation. You want to use the command ActionHomomorphism. For example:

gap> g:=DihedralGroup(IsPermGroup,12);
Group([ (1,2,3,4,5,6), (2,6)(3,5) ])
gap> b:=Blocks(g,MovedPoints(g),[1,4]);
[ [ 1, 4 ], [ 2, 5 ], [ 3, 6 ] ]
gap> act:=ActionHomomorphism(g,b,OnSets);
<action homomorphism>
gap> Image(act);
Group([ (1,2,3), (2,3) ])


Here the numbers 1,2,3 correspond to the permuted objects, i.e. 2 corresponds to the set [2,5]. I believe this is what you're looking for.

Note that the range (codomain) of an action homomorphism is $S_n$ by default, you can make it surjective by giving the extra last argument "surjective".

• Thanks, that's what I was looking for. Aug 19, 2015 at 15:05
• But can't upvote without 15 rep points. Aug 19, 2015 at 15:05