On Fri, Dec 28, 2012 at 12:27 PM, David Roe <roed.m...@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
> On Fri, Dec 28, 2012 at 2:36 AM, Jernej Azarija <azi.std...@gmail.com>
> 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 <azi.s...@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.
>>>
>>> >>
>>> >> 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 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.
>
>
--
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.
