<p>You can do much better than checking all n! permutations when brute forcing a solution, <a href="http://oeis.org/A186202" rel="nofollow">http://oeis.org/A186202</a>  The grail is showing that you can't do much better than that, or exploiting the fact that most graphs have no symmetry in them and using this to speed calculation.</p>

CC BY-SA 3.0
2012-11-29T23:46:55.120Z
The paper of yours referenced from OEIS shows a bound on the size of a set $S \subseteq S_n$ such that $S$ intersects every nontrivial subgroup of $S_n$. I'm probably just being slow here, but how does having such a set help you solve either a) the hidden subgroup problem for $S_n$ or b) graph isomorphism (a special case of (a))?
Joshua Grochow
CC BY-SA 3.0
2012-11-30T20:00:55.390Z
If you test one nontrivial permutation from each prime cycle you have checked every possible subgroup of Sn. It is still huge. Also, it is for checking graph automorphism which is "easier" than isomorphism.
Chad Brewbaker
CC BY-SA 3.0
2012-11-29T22:45:35.187Z
2012-11-29T22:45:35.187Z
Chad Brewbaker
<p>There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed promising, was proved to be incomplete for general graphs in this <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r120">paper</a> by Amir Rahnamai Barghi and Ilya Ponomarenko. Other similar approach was also refuted in <a href="http://arxiv.org/abs/1004.0206">this paper</a>
by Jamie Smith. In both of these papers, they use the idea of <em>coherent configuration (schemes)</em> and alternative but equivalent formulation of <em>cellular algebra</em> (matrix subalgebra indexed by a finite set -here vertex set- closed under point-wise multiplication, complex conjugate transpose, and containing Identity matrix <strong>I</strong> and all-one matrix <strong>J</strong>) respectively to provide necessary counter arguments.</p>

<p>I find it very difficult to follow those arguments and even if I follow individual arguments vaguely I do not understand the core idea. I would like to know if the essence of the arguments can be explained in generic terms -may be at the cost of slight rigour- without using  the language of scheme theory or cellular algebra.</p>

<cc.complexity-theory><graph-theory><graph-algorithms><graph-isomorphism>
Negative results on identical particles approach to Graph Isomorphism (GI) problem
DurgaDatta
# Negative results on identical particles approach to Graph Isomorphism (GI) problem

(Asked by: username_0 on 2012-11-29)

There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed promising, was proved to be incomplete for general graphs in this [paper](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r120) by Amir Rahnamai Barghi and Ilya Ponomarenko. Other similar approach was also refuted in [this paper](http://arxiv.org/abs/1004.0206)
by Jamie Smith. In both of these papers, they use the idea of *coherent configuration (schemes)* and alternative but equivalent formulation of *cellular algebra* (matrix subalgebra indexed by a finite set -here vertex set- closed under point-wise multiplication, complex conjugate transpose, and containing Identity matrix **I** and all-one matrix **J**) respectively to provide necessary counter arguments.

I find it very difficult to follow those arguments and even if I follow individual arguments vaguely I do not understand the core idea. I would like to know if the essence of the arguments can be explained in generic terms -may be at the cost of slight rigour- without using the language of scheme theory or cellular algebra.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, graph-isomorphism


---

## 1 answers

### Answer by username_1 on 2012-11-29. Score: 4 | Accepted answer

You can do much better than checking all n! permutations when brute forcing a solution, <http://oeis.org/A186202> The grail is showing that you can't do much better than that, or exploiting the fact that most graphs have no symmetry in them and using this to speed calculation.

> **Comments:**
> **username_2**: The paper of yours referenced from OEIS shows a bound on the size of a set $S \subseteq S_n$ such that $S$ intersects every nontrivial subgroup of $S_n$. I'm probably just being slow here, but how does having such a set help you solve either a) the hidden subgroup problem for $S_n$ or b) graph isomorphism (a special case of (a))?  
> **username_1**: If you test one nontrivial permutation from each prime cycle you have checked every possible subgroup of Sn. It is still huge. Also, it is for checking graph automorphism which is "easier" than isomorphism.  

---

