Inconsitent output of the domain for the automorphism group of graph?

[Jernej Azarija]

Hello!

I apologize for posting this question here but somehow I am not allowed to drop questions to sage-support. Moreover I do not feel confident enough to post this thing as a bug on the trac wiki.

Working with a large graph G on ~250 vertices I have noticed that elements of the automorphism group of G permute ~50 vertices and that most vertices are fixed by any automorphism. Hence most orbits of the automorphism group contain just singletons. However sage simply discards all vertices that are fixed by the automorphism . In my case this resulted in an "incomplete" orbit containing just 50 elements. An extreme case happens when one deals with an asymmetric graph

===
sage: G = graphs.RandomRegular(7,50)
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
sage: G.automorphism_group().domain()
{1}
sage: G.automorphism_group().orbits()
[[1]]
===

This of course is not the desired result since one assumes orbits partition the group.

Is this a bug or am I simply missing some parameter to resolve this issue?

[Benjamin Jones]

I don't think this is a bug.

It looks to me like G.automorphism_group() is returning an abstract
permutation group. For a lot of random graphs this is going to be the
trivial group "Permutation Group with generators [()]" (a random graph
is likely to have no symmetry). The natural (non-empty) domain for the
action of such a group is a singleton set and there is of course only
one orbit there. Notice that G.automorphism_group().domain() returns
{1}, it's the domain of a permutation group on {1, ... , n}.

I guess what you want is the automorphism group along with it's action
on the set of vertices of the graph.

One simple thing you can do is call:

sage: A = G.automorphism_group(orbits=True)

to get the abstract group back along with the set of orbits. Also, by
setting `translation=True` you can also get a dictionary back that
provides translation from vertices {0, 1, ..., n} to the domain set of
the permutation group (a subset of {1, ... , n+1}).

--
Benjamin Jones

[kcrisman]

>
> Is this a bug or am I simply missing some parameter to resolve this issue?
>

I don't think this is a bug.

It looks to me like G.automorphism_group() is returning an abstract
permutation group. For a lot of random graphs this is going to be the
trivial group "Permutation Group with generators [()]" (a random graph
is likely to have no symmetry). The natural (non-empty) domain for the
action of such a group is a singleton set and there is of course only
one orbit there. Notice that G.automorphism_group().domain() returns
{1}, it's the domain of a permutation group on {1, ... , n}.

I guess what you want is the automorphism group along with it's action
on the set of vertices of the graph.

One simple thing you can do is call:

sage: A = G.automorphism_group(orbits=True)

to get the abstract group back along with the set of orbits. Also, by
setting `translation=True` you can also get a dictionary back that
provides translation from vertices {0, 1, ..., n} to the domain set of
the permutation group (a subset of {1, ... , n+1}).

--

Hmm, that is very useful to me as well.  Thanks! 

[Jernej Azarija]

Hello! Thanks for your reply!

It looks to me like G.automorphism_group() is returning an abstract
permutation group. For a lot of random graphs this is going to be the
trivial group "Permutation Group with generators [()]" (a random graph
is likely to have no symmetry). The natural (non-empty) domain for the
action of such a group is a singleton set and there is of course only
one orbit there. Notice that G.automorphism_group().domain() returns
{1}, it's the domain of a permutation group on {1, ... , n}.

I am not sure this is consistent with the mathematical definition of the domain of a group acting on a set S. Even *if* I take this convention for granted, it becomes a mess if I try to obtain the orbits of a vertex-stabilizer. Being more concrete:

sage: G = graphs.RandomRegular(7,50)
sage: G.automorphism_group().stabilizer(1).orbits()
[[1]]

which is clearly not the desired output.

 

I guess what you want is the automorphism group along with it's action
on the set of vertices of the graph.

 

One simple thing you can do is call:

sage: A = G.automorphism_group(orbits=True)

Yes. Is there a way to extend this answer to the case when I wish to obtain the orbit of a specific subgroup of the automorphism group?

[Benjamin Jones]

G.automorphism_group() is not returning "a group acting on a set S",
merely a permutation group. Observe that the trivial group is
isomorphic to the trivial permutation subgroup of {1} as well as {0,
1, ... , 50}.

> Even *if* I take this convention for
> granted, it becomes a mess if I try to obtain the orbits of a
> vertex-stabilizer. Being more concrete:
>
> sage: G = graphs.RandomRegular(7,50)
> sage: G.automorphism_group().stabilizer(1).orbits()
> [[1]]
>
> which is clearly not the desired output.

This in consistent with what I said above. In this case
G.automorphism_group() is the trivial group (permutation group with no
generators). So, G.automorphism_group().stabilizer(1) is again the
trivial group.

>>
>> One simple thing you can do is call:
>>
>> sage: A = G.automorphism_group(orbits=True)
>
> Yes. Is there a way to extend this answer to the case when I wish to obtain
> the orbit of a specific subgroup of the automorphism group?
>

The documentation (G.automorphism_group?) describes how to get the
subgroup of the automorphism group that preserves a given partition of
the vertex set. Other than that it would depend on what subgroup you
want. Check out the generic group methods that construct subgroups.

Also, see this discussion:
https://groups.google.com/forum/?fromgroups=#!topic/sage-support/HX0QfXgwO5s

--
Benjamin Jones

[Jernej Azarija]

Right!

The problem occurs when you have a larger graph (say on vertices V = { 0,...,150}) whose automorphism group is not trivial. Moreover suppose the stabilizer of a given vertex v is not trivial. Then sage "will cast" the stabilizer of v to be a permutation group on the set S = {1....k} and the information about the structure of the stabilizer is lost since you do not know which vertex from S is mapped to which vertex of V.

>>
>> One simple thing you can do is call:
>>
>> sage: A = G.automorphism_group(orbits=True)
>
> Yes. Is there a way to extend this answer to the case when I wish to obtain
> the orbit of a specific subgroup of the automorphism group?
>

The documentation (G.automorphism_group?) describes how to get the
subgroup of the automorphism group that preserves a given partition of
the vertex set. Other than that it would depend on what subgroup you
want. Check out the generic group methods that construct subgroups.

Yeah but then again if I am looking for a certain subgroup (like a regular subgroup of the automorphism group etc..) I always lose the vertex->elements map in doing computations with the PermuationGroups class.

 

Also, see this discussion:
https://groups.google.com/forum/?fromgroups=#!topic/sage-support/HX0QfXgwO5s

Thanks for the link and useful discussion!

Best,

Jernej

 

--
Benjamin Jones

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To post to this group, send email to sage-...@googlegroups.com.
To unsubscribe from this group, send email to sage-devel+...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[Jernej Azarija]

The documentation about the partition thing is quite shallow (just one sentence) and the expected usage does not seem to work:
===
sage: G = graphs.PetersenGraph()
sage: G.automorphism_group(partition=[[1]])
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)

/home/foo/<ipython console> in <module>()

/home/foo/sage-5.5.rc0/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in automorphism_group(self, partition, translation, verbosity, edge_labels, order, return_group, orbits)
  16466             HB = H._backend
  16467             for u,v in self.edge_iterator(labels=False):
> 16468                 u = G_to[u]; v = G_to[v]
  16469                 HB.add_edge(u,v,None,self._directed)
  16470             GC = HB._cg

KeyError: 0
 
=====

does anyone happen to know how is this thing used? I need to compute the automorphism group that fixes the specified vertex (the stabilizer of a vertex v of the automorphism of G)

[David Roe]

In the long term, I think the right solution is to copy what is done for Galois groups of number fields: depending on a keyword option to automorphism_group(), we should return either the abstract permutation group (as is done now) or a group equipped with an action on the edges and vertices of the graph.

David

--

[Benjamin Jones]

>>
>> The documentation (G.automorphism_group?) describes how to get the
>> subgroup of the automorphism group that preserves a given partition of
>> the vertex set.
>
> The documentation about the partition thing is quite shallow (just one
> sentence) and the expected usage does not seem to work:
> ===
> sage: G = graphs.PetersenGraph()
> sage: G.automorphism_group(partition=[[1]])
> ---------------------------------------------------------------------------
> KeyError Traceback (most recent call last)
>
> /home/foo/<ipython console> in <module>()
>
> /home/foo/sage-5.5.rc0/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc
> in automorphism_group(self, partition, translation, verbosity, edge_labels,
> order, return_group, orbits)
> 16466 HB = H._backend
> 16467 for u,v in self.edge_iterator(labels=False):
>> 16468 u = G_to[u]; v = G_to[v]
> 16469 HB.add_edge(u,v,None,self._directed)
> 16470 GC = HB._cg
>
> KeyError: 0
>
> =====
>
> does anyone happen to know how is this thing used? I need to compute the
> automorphism group that fixes the specified vertex (the stabilizer of a
> vertex v of the automorphism of G)

The partition you give should be a partition of the vertex set.
`partition=[[1]]` would only work if you had a vertex set {1}. Here
are some examples:

sage: G = graphs.PetersonGraph()
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: G.automorphism_group(partition=[[0], [1..9]])
Permutation Group with generators [(3,7)(4,5)(8,9),
(2,6)(3,8)(4,5)(7,9), (1,4,5)(2,3,8,6,9,7)]
sage: G.automorphism_group(partition=[[0,1,2], [3..9]])
Permutation Group with generators [(3,7)(4,5)(8,9), (2,10)(3,5)(4,7)]

--
Benjamin Jones

[Benjamin Jones]

On Fri, Dec 28, 2012 at 12:27 PM, David Roe <roed...@gmail.com> wrote:
> In the long term, I think the right solution is to copy what is done for
> Galois groups of number fields: depending on a keyword option to
> automorphism_group(), we should return either the abstract permutation group
> (as is done now) or a group equipped with an action on the edges and
> vertices of the graph.
> David
>

This is a good idea. For the lurkers, azi created ticket #13874 for this.

--
Benjamin Jones

[Jernej Azarija]

Right!

However, I haven't proposed the full modification as David suggested! Can someone of you two guys add a more detailed request to this trac ticket since I am not perfectly aware of what needs to be done?

Best,

Jernej

[Jason Grout]

Until we have proper support for this, you can do:

sage: g=Graph({'a': 'b', 'b': 'c'})
sage: p,q=g.automorphism_group(translation=True)
sage: pp=PermutationGroup(gap_group=p._gap_(), domain=sorted(q, key=q.get))

sage: pp
Permutation Group with generators [('c','a')]

(this also helps you see how to implement it...)

Unfortunately, there is a bug in the stabilizer method when the
permutation group has a custom domain, which is now fixed at
http://trac.sagemath.org/sage_trac/ticket/13893, which now needs review.

a workaround for the stabilizer bug is:

sage: pp.subgroup(gap_group=gap.Stabilizer(pp, pp._domain_to_gap['b']))
Subgroup of (Permutation Group with generators [('c','a')]) generated by
[('c','a')]


Thanks,

Jason