Ask Your Question
0

Does Sage keep the order of vertices in a graph and it's group or scramble them? For me it sometime scrambles them.

asked 2012-09-12 05:20:15 -0500

LouChaos gravatar image

I use the Sage automorphism_group function to find the group that leaves an adjacency matric, say C, invariant under a similarity transformation. But sometimes it seems the results are for matrices on a vertex space that is not the same as the original, but is reordered.

A simple example on a 3-vertex graph: o--o--o.

with index order               1  0  2

Adjacency matrix= C =

 [0 1 1]
 [1 0 0]
 [1 0 0]

The group is the identity and a reflection about the center vertex:

[1 0 0]       [0 1 0]
[0 1 0]  and  [1 0 0] = R
[0 0 1]       [0 0 1]

I would have expected the reflection to be,

[1 0 0]
[0 0 1]
[0 1 0],

but R is what Sage gives.

Sure enough, RCR^-1 gives the following,

[0 1 0]
[1 0 1]
[0 1 0]

which is not the original C matrix. However the R transformation leaves the matrix

[0 0 1]
[0 0 1] = C'
[1 1 0]

invariant. The last matrix is the C matrix where the vertices are indexed in reverse order.

Does Sage have some canonical way it orders the vertices in graphs and groups?

A bit more info, maybe. The order of the irreducible representation table seems to give a hint. If the trivial representation is the first row (which it is for some graphs), it appears (from a few tests) that the vertices retain their original order to align with C. If the trivial representation is the last row then the matrix C' is the adjacency matrix (suggesting a reordering of the vertices). I have no idea why this should be related if it is.

Bottom line for me is I cannot apply any matrices from the group that come from the matrix() method to C or other objects in my original vertex space since they are ordered differently. I don't see how to find the vertex order sage uses. Any help or insight appreciated.

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
1

answered 2012-09-12 06:54:34 -0500

kcrisman gravatar image
sage: G = graphs.PathGraph(3)
sage: G
Path Graph: Graph on 3 vertices
sage: H = G.automorphism_group()
sage: H
Permutation Group with generators [(2,3)]

So that sounds like not necessarily connected, especially since GAP (our group engine) notation starts counting at one, but our graphs (like most Python stuff) starts at zero. That said,

sage: G.automorphism_group??

could give you some clues. Sorry. In this case, a group is just a group. Is there a theorem that says there should be a connection? It's not as if we are giving a subgroup of the easy representation of the permutation group on all vertices; I can't find a matrix() method for G or H.

edit flag offensive delete link more

Comments

Thanks for the answer Kcrisman. I looked at automorphism_group?? and I may have found the answer. There is a keyword option 'translation' which gives a dict for mapping from vertices of the graph (dict keys using python indexing from 0) to the permutation elements (1,2,3,...) which must be positive integers. When I printed the dict for a simple graph the 0th vertex is mapped to the last integer, the others appear to be mapped to the same integer as the python index (since those are positive and non-zero). Does this sound right? I will be experimenting with this "reordering" and I'll let you know if it worked. Thanks, you might have solved another group-graph puzzle for me.

LouChaos gravatar imageLouChaos ( 2012-09-12 07:40:10 -0500 )edit

yes, typically the mapping from a graph with vertices 0..n-1 in Sage in situations like these is done by making vertex 0 vertex n. That way most of the vertices have the same numbers.

Jason Grout gravatar imageJason Grout ( 2012-09-14 18:40:19 -0500 )edit
0

answered 2012-09-12 11:40:13 -0500

LouChaos gravatar image

I found there is a translation table keyword option for the automorphism_group() call which returns a table showing which vertex indices (which go from 0 to n-1, where n is the group order) match the cycle labels (which go from 1 to n since they must all be > 0 integers). The table tells you how Sage is internally ordering the vertices so you can match up the output group matrices with your original vertex vector space. This helps align your adjacency matrix with the outputs from the automorphism_group method and other items calculated from that group like the matrices.

Get more info by typing D.automorphism_group?? where D is a graph based on your input adjacency matrix.

Thanks to krisman for suggesting I look at D.automorphism_group?? info.

edit flag offensive delete link more

Comments

I meant kcrisman, sorry.

LouChaos gravatar imageLouChaos ( 2012-09-12 12:44:44 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-09-12 05:20:15 -0500

Seen: 351 times

Last updated: Sep 12 '12