On May 16, 7:29 pm, Robert Miller <r...@rlmiller.org> wrote: > On Mon, Apr 26, 2010 at 4:59 PM, Dima Pasechnik <dimp...@gmail.com> wrote: > > I work a lot with (large, say, 5000 vertices) (di)graphs having large > > automorphism groups (often vertex-transitive, etc). > > You should post up some examples somewhere, so I can get a sense of > Sage's performance with these kinds of graphs.
for instance, take a hypercube, H(n,2), and fixed 0<k_0<k_1, and form the graph Gamma on its 2^n vertices, so that two vertices of Gamma are adjacent if they are at distance between k_0 and k_1 in H(n,2). > > > Such graphs are very efficiently represented in GAP (via GRAPE) > > package. > > (one needs to keep representatives of arc orbits, and few other > > things, to be able to check adjacency of vertices, say) > > These kinds of graphs often arise in e.g. coding theory. > > Is there anything like this in Sage? > > Everything you've described can be done in Sage, but I think that's > not quite the question. There aren't any specialized data structures > for keeping track of these things, just the usual digraph objects and > permutation group objects. > > > My primary use of Sage is an interface between GAP and cvxopt, so e.g. > > I can compute such graph invariants as > > Lovasz theta-function. The size of graphs makes it mandatory to use a > > compact representation, and > > "collapsed" adjacency matrices, that carry enough information about > > underlying algebra (e.g. graph eigenvalues). > > It would be helpful if you could explain these in a bit more detail. > E.g. are these graphs highly sparse? no, they are not sparse. In fact, if you have a permutation group G on n points, then the collection of adjacency matrices of the arc-transitive G-invariant digraphs (loops allowed) forms an subalgebra A(G) of M_n(C). This algebra has many names, e.g. "coherent configuration", or, when G is transitive, "(non-commutative association scheme"). If one is interested in, e.g., the eigenvalue information of a G- invariant graph, the adjacency matrix of this graph is in A(G), and this information can be recovered from another faithful representation of A(G), e.g. the regular representation. And the basis of the latter can be obtained, as usual, from the multiplication coefficients of A(G), which in turn are easy to compute; I have developed a GAP package that does these things, see http://www1.spms.ntu.edu.sg/~dima/pubs/cohcfg-shortnote.pdf More generally, if one is interested in solving a G-invariant semidefinite programming problem, e.g. compute the Lovasz theta-function of a G-invariant graph, this can be done in the space of a faithful representation of A(G), instead of the original space (e.g. in the hypercube example one would work with nxn matrices, instead of 2^n x 2^n matrices) Right now, for computing Lovasz theta, I have a crude Sage code that calls my GAP package, gets the regular representation matrices from it, and calls cvxopt's semidefinite programming solver to compute Lovasz theta. But if one would give me a Sage graph, and asks me to compute Lovasz theta, I would need to compute a compact representation of such a graph (GRAPE-like, i.e. a transversal of the arc orbits of the automorphism group of the graph, and the group itself), and only then pass it on to my code. It looks as if in the long run one might like to have coherent configurations code/data directly in Sage... Hope this explains something, Dima > > > I wonder if Sage should get its own "graph with symmetries" class > > (unless there is already one...) > > There isn't one. Right now even the automorphism group itself could be > better, since the vertices and the points that get permuted aren't > even the same. There is plenty of room for improvement... > > > Dima > > -- > Robert L. Millerhttp://www.rlmiller.org/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
