GAP function to convert a subgroup lattice to a simple graph?

Question

I've been using XGAP to view the subgroup lattices of various groups, and I am interested in their properties as simple graphs. I need a program that, given a group G, can output the subgroup lattice of G as a simple graph; that is, as a set V of vertices and a set E of edges.

Does such a function exist?

I have looked into GRAPE and DIGRAPH to no avail.

Answer 1

You might look at DotFileLatticeSubgroups, which outputs the subgroup lattice to a dot file visualizable by GraphViz. It'd be easy to modify this (or alternatively, to postprocess its output) to get a list of vertices and edges. I agree that it'd be nice to have a clean way to get a list of edges out of a subgroup lattice sheet. Perhaps something under the Poset menu?

PS: You mention xgap. If you have a Mac handy, you might enjoy my slightly more modern take, Gap.app

UPDATE: I wrote a function that will take a GraphicSubgroupLattice and return a list of edges of the represented Hasse diagram. To use it, type
L:=GraphicSubgroupLattice(DihedralGroup(8));
then get the subgroups you'd like to look at in the Hasse diagram (e.g. by doing Subgroups | All Subgroups), then type
GraphicLatticeToGraph(L);
I expect that it will also work with other poset objects in xgap/Gap.app, but have not tested it.

The function follows.

GraphicLatticeToGraph:=function(L)
  local Gr, lev, cl, H, M;

  Gr:=[];

  for lev in L!.levels do
    for cl in lev!.classes do
      for H in cl do
        for M in H!.maximals do
          AddSet(Gr, [M!.label, H!.label]);
        od;
      od;
    od;
  od;
  return Gr;
end;

Answer 2

I don't know if such a function exists in GAP proper, but you can definitely use sage to do it. Sage has a wrapper for GAP, which will let you use all the features you're used to, in addition to many more (which might be relevant in this situation).

In particular, the following code should do what you want. You can modify it to return a DiGraph object, a Poset, or any number of things. In particular, if you want to work with the vertex and edge sets directly, there's methods for that. Take a look at the graph library for more info. You can also check out this blog which has some details on working with subgroup lattices in sage. Keep in mind, though, that the blog was written back when sage used python 2.7, so you'll have to make some cosmetic changes to get the example code to run.

def subgroupLatticeAsGraph(G):
    subs = G.subgroups()
    areRelated = lambda H,K: H != K and (H.is_subgroup(K) or K.is_subgroup(H))
    return Graph([subs, areRelated])

---

I hope this helps ^_^

Answer 3

Here is a way to construct such a graph with the GRAPE package, starting with subgroup class representatives as seeds:

gap> G:=SymmetricGroup(4);; # or whatever group you want
gap> cl:=ConjugacyClassesSubgroups(G);;
gap> reps:=List(cl,Representative);;
gap> gamma:=Graph(G,reps,OnPoints,IsSubset);;

Here we use that the group G acts on its subgroups, reps contains representatives of all orbits, the action of a group element on a subgroup is by OnPoints (i.e. via the ^ operator), and the edge relation we want is given by IsSubset. (If you want to revert the relation use

function(x,y) return IsSubset(y,x);end

instead. If you want to make the graph undirected use

function(x,y) return IsSubset(y,x) or IsSubset(y,x);end

instead. Now the graph gamma contains a component names that gives the correspondence of subgroups to index numbers.