Hacker News new | comments | show | ask | jobs | submit login

Is there a layman-readable proof or proof-sketch of the reduction from Group Isomorphism to Graph Isomorphism? Is the method constructive, so that every group reduces to a corresponding graph in an understandable way?

I have a somewhat cranky reason for asking. In evolutionary algorithms, a mutation operator is one which transforms an existing genome into a single new one. One can study the behaviour of an operator by drawing an edge from old to new genomes, for every possible genome, and studying the resulting graph. A crossover operator takes two parent genomes to produce a new one. No-one really has a satisfactory method of studying crossover analogous to that for mutation. The problem is we need edges to lead from pairs of nodes to single nodes. So kind of like hyperedges but not exactly. I've been hoping for a while that there is an answer in existing graph theory.

Crossover is also kind of like a group operation, but again not exactly. So that's why the idea of mapping a group to a graph is interesting.




You might want to look at the definition of Cayley graphs : http://en.m.wikipedia.org/wiki/Cayley_graph




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: