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 On Friday, 28 December 2012 22:05:38 UTC+1, Benjamin Jones wrote: > > On Fri, Dec 28, 2012 at 12:27 PM, David Roe <[email protected]<javascript:>> > 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 > > > > On Fri, Dec 28, 2012 at 2:36 AM, Jernej Azarija > > <[email protected]<javascript:>> > > > wrote: > >> > >> > >> > >> On Thursday, 27 December 2012 23:51:07 UTC+1, Benjamin Jones wrote: > >>> > >>> On Thu, Dec 27, 2012 at 1:07 PM, Jernej Azarija <[email protected]> > >>> 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 < > [email protected]> > >>> >> 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. > >>> > >>> >> > >>> >> 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. > >> > >> 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) > >> > >>> 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 > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "sage-devel" group. > >> To post to this group, send email to > >> [email protected]<javascript:>. > > >> To unsubscribe from this group, send email to > >> [email protected] <javascript:>. > >> 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 > > [email protected]<javascript:>. > > > To unsubscribe from this group, send email to > > [email protected] <javascript:>. > > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
