4 ms·
Another interesting algebraic structure on graphs is the automorphism group of graphs. For a graph G, the automorphism group is the set of functions f: G -> G s
by openasocket 10y ago
Another interesting algebraic structure on graphs is the automorphism group of graphs. For a graph G, the automorphism group is the set of functions f: G -> G such that if (and only if) nodes x and y have an edge between them, f(x) and f(y) have an edge between them. You can think of each such automorphism as a symmetry of the graph. Some very interesting work has been done with this abstraction. In fact, I believe the recent paper claiming to solve the Graph Isomorphism problem in polynomial time makes heavy use of this.
- Chris_Newton 10y agoDo you have a reference for that paper about graph isomorphism, please?
- OJFord 10y agoI believe the parent commenter is probably referring to Laszlo Babai's late-2015 paper on quasipoly GI: https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algo...
- openasocket 10y agohttps://arxiv.org/abs/1512.03547 https://arxiv.org/abs/1512.03547 Note it was actually Quasipolynomial time, not true polynomial time. It's also a pretty recent paper, so it could turn out to have flaws.
- JadeNB 10y ago> It's also a pretty recent paper, so it could turn out to have flaws. On the other hand, it's Babai, so it doesn't. :-)