ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 13 Jan 2022 10:31:03 +0100Graph Automorphisms as Permutation Matriceshttps://ask.sagemath.org/question/60661/graph-automorphisms-as-permutation-matrices/I am trying to take the automorphism group of a finite graph as a permutation group, and then have that permutation group act on R^{vertices of the graph} by permuting coordinates of points. However, when I convert the group elements to permutation matrices, sage seems to sometimes relabel the vertices of the graph, causing the group to act incorrectly. I noticed the problem with the wheel graph. I ran the following four lines in a sagemath jupyter notebook.
W5 = graphs.WheelGraph(5); W5
(I can't include the output since I can't attach pictures, but the important thing is that the middle vertex, which is fixed by all automorphisms, is labelled 0).
W5.adjacency_matrix()
`[0 1 1 1 1]`
`[1 0 1 0 1]`
`[1 1 0 1 0]`
`[1 0 1 0 1]`
`[1 1 0 1 0]`
(The adjacency matrix above is included as evidence that the center vertex is indeed indexed 0.)
aut = W5.automorphism_group(); aut.list()
`[(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3)]`
g=aut.an_element(); g
`(1,2,3,4)`
g.matrix()
`[0 1 0 0 0]`
`[0 0 1 0 0]`
`[0 0 0 1 0]`
`[1 0 0 0 0]`
`[0 0 0 0 1]`
I suspect that the problem occurs because the vertex 0 is fixed by *all* automorphisms. Notice that when the group element is converted to a matrix, the indexing seems to change from 0,..,4 to 1,..,5 with the last coordinate fixed instead of the first. I also tested the cycle graph, and here the problem does not occur, even when I choose a group element that fixes vertex 0:
C5 = graphs.CycleGraph(5); C5
(Again, I can't include a picture, but the vertices are numbered 0 to 4)
autcycle = C5.automorphism_group(); autcycle.list()
`[(),
(0,4,3,2,1),
(0,3,1,4,2),
(0,2,4,1,3),
(0,1,2,3,4),
(1,4)(2,3),
(0,4)(1,3),
(0,3)(1,2),
(0,2)(3,4),
(0,1)(2,4)]`
gcycle = autcycle.random_element(); gcycle
`(1,4)(2,3)`
gcycle.matrix()
`[1 0 0 0 0]`
`[0 0 0 0 1]`
`[0 0 0 1 0]`
`[0 0 1 0 0]`
`[0 1 0 0 0]`
I think this is a bug, but if not, I would love some tips on how to achieve my expected outcome. Thank you!
mjsupinaThu, 13 Jan 2022 10:31:03 +0100https://ask.sagemath.org/question/60661/Graph automorphism group and its source codehttps://ask.sagemath.org/question/55801/graph-automorphism-group-and-its-source-code/ I am looking for the source code of graph automorphism_group function. In GitHub, there are different automorphism group functions, so I am kind of lost because there are also NAUTY functions or bliss.
I am curious about how SAGE graph automorphism group function works. I assume that an automorphism group of a graph is constructed based on row entries. If we have adjacency matrix of a graph, starting with initial partition, the partition is refined for each row until the discrete partition is reached. These partitions are used for the construction of coset representatives (or transversals) for each row. The multiplication of these representatives returns us the automorphism group of the graph.
Can someone inform me about SAGE's graph automorphism group method and its source code ?
MehmetAzizYirikSun, 21 Feb 2021 19:38:15 +0100https://ask.sagemath.org/question/55801/