Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Question:

Given a finite simplicial complex $K$, what general techniques allow one to efficiently compute (a presentation of) the group $\text{Aut}(K)$ of $K$'s automorphisms?

Since this is strictly harder than the corresponding problem for graphs (often solved using NAUTY), one shouldn't expect a universally efficient answer, so I'm only looking for implementations of good heuristics, a la NAUTY. Both GAP and SAGE have some implementations which do the job, but I'm wondering if it is possible to know what the underlying algorithms are without having to read through the source code.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

In Sage, at least, the documentation suggests what algorithm is used:

This is done by creating a bipartite graph, whose vertices are
vertices and facets of the simplicial complex, and computing its
automorphism group.

(I wouldn't be surprised if Sage called GAP to do this graph computation, by the way.)

share|improve this answer
    
as a matter of fact Sage doesn't call GAP here (nor anywhere else on graph automorphisms, in fact). GAP also doesn't do graph automorphsims "natively", it uses a package called GRAPE. Which calls nauty, in fact... –  Dima Pasechnik Sep 19 '13 at 1:31
    
Hi Dima. Ah, okay. I was looking at the code in the original patch (as linked in the question), and it had variables with names like simpl_to_gap, so that's what led me to believe that. I see the current source code doesn't have those anymore. –  John Palmieri Sep 19 '13 at 3:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.