On Thu, Dec 27, 2012 at 11:51 PM, Benjamin Jones
<benjaminfjo...@gmail.com>wrote:
> On Thu, Dec 27, 2012 at 1:07 PM, Jernej Azarija <azi.std...@gmail.com>
> wrote:
> >
> >
> > On Thursday, 27 December 2012 20:59:45 UTC+1, Benjamin Jones wrote:
> >>
> >> On Thu, Dec 27, 2012 at 11:39 AM, Jernej Azarija <azi.s...@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.
> >
> >
> > 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.
>
> 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.
>
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-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.
>
>
>
--
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.
