Opened 8 years ago
Last modified 6 years ago
#13874 new enhancement
Allow automorphism group of a graph to act on the graph's vertex set
Reported by: | azi | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | graph theory | Keywords: | |
Cc: | rbeezer, ncohen, dcoudert, benjaminfjones | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The current implementation of the automorphism group of a graph always relabels the graph in question to use the vertex set {1,2,...,n+1} and then returns the automorphism group based on this labeling and potentially a translation for the labeling as well.
Needless to say that this is time consuming, confusing and also prone to bugs since if one uses integers as labels (starting at 0 for example) the relabeling might go unnoticed.
As it appears from this sage-devel post it is now possible to use arbitrary domains for permutation groups.
Hence, it would be nice to integrate this change into the automorphism_group function as well.
From https://groups.google.com/d/msg/sage-devel/y_TuGhjLYJQ/8YBUmQaNsXUJ
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
--- Also what appears to be a 'defect' is that if you have a graph G on say 150 vertices and you want to compute the stabilizer (or some other subgroup..) of Aut(G) and you do
A = G.automorphism_group() S = A.stabilizer(v)
it happens that you lose the information about the vertices of G. Since S can be a group on a smaller domain and there is no translation from it to the vertices of G
Change History (8)
comment:1 Changed 8 years ago by
- Cc benjaminfjones added
comment:2 Changed 8 years ago by
- Description modified (diff)
- Summary changed from Allow automorphism of groups to work on the original vertex set to Allow automorphism group of a graph to act on the graph's vertex set
comment:3 Changed 8 years ago by
- Description modified (diff)
comment:4 Changed 8 years ago by
comment:5 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:6 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:7 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:8 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
I posted this to the mailing list, but it's relevant here too:
Until we have proper support for this, you can do:
(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 #13893, which now needs review.
a workaround for the stabilizer bug is: