Room for Jim and Thomas Klimpel

Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism. My hope for such an algorithm comes from reading a blog post on the group isomorphism problem and its comments. Becau...

The thing is that the Cayley graph is not canonical : for a given group $G$, each choice of a generating set will give a different Cayley graph. And every group with at least $3$ elements has a Cayley graph with triangles : if $x\neq y$ in $G$, put $x$, $y$ and $xy^{-1}$ in the generating set, a...

The following very simple answer addresses worst-case complexity. How to do the reduction in practice would be a different question, as would average complexity (as pointed out by logicute). For a graph $G$, let $\hat{G}$ denote the barycentric subdivision of $G$. This is triangle-free. I claim ...

Is there an approach to graph isomorphism considering that we are already given a partial isomorphism ? In particular, it would be interesting to have conditions on this partial isomorphism that makes the problem polynomial. This question arises from automata theory, where one approach to testin...

We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any cell $C$, it holds that $v,w$ have the same number of neighbours in $C$. The trivial partition (w...

I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result. Question 1. Let $G$ be a simple undirected graph of order $n$. What is the computational complexity (in terms of $n$) of determining if $G$ is vertex-transitive? Recal...