On Thu, Dec 27, 2012 at 11:39 AM, Jernej Azarija <azi.std...@gmail.com> wrote:
> 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?
>
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
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
