[GAP Forum] Find a preserved partition given an imprimitive group action

[William DeMeo]

Dear Nathann,

To find out if a group is primitive, use the GAP command IsPrimitive.

Example:

gap> G:=TransitiveGroup(8,4);  # dihedral group of deg 8

gap> IsPrimitive(G);  # returns false

To see the blocks, use the command AllBlocks:

gap> AllBlocks(G);

[ [ 1, 2, 3, 8 ], [ 1, 6 ], [ 1, 3, 4, 6 ], [ 1, 3 ], [ 1, 3, 5, 7 ],
[ 1, 7 ], [ 1, 5 ], [ 1, 4 ] ]

The output of the last command shows one block for each "system of
imprimitivity" or "congruence."  To see the full set of systems of
imprimitivity (the full congruence lattice), you could do something
like this:

gap> for b in AllBlocks(G) do Print(Orbit(G,b,OnSets), "\n"); od;
[ [ 1, 2, 3, 8 ], [ 4, 5, 6, 7 ] ]
[ [ 1, 6 ], [ 2, 7 ], [ 3, 4 ], [ 5, 8 ] ]
[ [ 1, 3, 4, 6 ], [ 2, 5, 7, 8 ] ]
[ [ 1, 3 ], [ 2, 8 ], [ 4, 6 ], [ 5, 7 ] ]
[ [ 1, 3, 5, 7 ], [ 2, 4, 6, 8 ] ]
[ [ 1, 7 ], [ 2, 4 ], [ 6, 8 ], [ 3, 5 ] ]
[ [ 1, 5 ], [ 2, 6 ], [ 3, 7 ], [ 4, 8 ] ]
[ [ 1, 4 ], [ 2, 5 ], [ 3, 6 ], [ 7, 8 ] ]

Hope that helps.

-William


On Sun, Jun 10, 2012 at 7:00 AM, Nathann Cohen <nathann.cohen at gmail.com> wrote:
> Helloooooo everybody !!!
>
> I am but a humble graph theoretician, and I recently ended up playing with
> the automorphism groups of my dear objects in order to find good ways to
> plot them. This I do directly with GAP when I do not use it through Sage,
> but I currently have a very technical problem and I would be delighted if
> you happened to have already implemented somewhere the feature I am looking
> for :-)
>
> Here it is : I have a permutation group G, or a group acting on a set of
> vertices in a graph, which sometime turns out to be imprimitive [1], which
> means (I learned that recently) that there exists a nontrivial partition P
> = P1, ... P_k of my set of vertices such that the  image of any P_i by an
> element of G is another element of P. I do not know yet whether GAP can
> tell me whether a given permutation group is primitive, but more than that
> I would be interested in obtaining -- when it is not the case -- an example
> of partition which is preserved in such a way.
> Actually, because I am *very* greedy, I would ideally like to obtain an
> inclusionwise "finest" (or smallest) partition, and in an ideal world to
> enumerate them all.
>
> May it be a task that GAP can solve ? :-)
>
> Thank you very much for your help !
>
> Nathann
>
> [1] http://en.wikipedia.org/wiki/Primitive_permutation_group
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum



-- 
William J. DeMeo, Ph.D.
Department of Mathematics
University of Hawaii at Manoa
phone: 808-298-4874
url: http://math.hawaii.edu/~williamdemeo