While determining the existence of Euler cycle (going once through each edge) for given graph is trivial, for Hamilton path (going once through each vertex) it is NP-complete problem (e.g. worth a million dollar). Denoting adjacency matrix of this graph by \(A\) and its number of vertices by \(n\), diagonal elements of \(A^n\) count also eventual Hamilton cycles – the problem is that they also count other length n cycles – going more than once through some vertex. The question is if we could somehow "subtract" those going multiple times through some vertex ... Grassman variables (anticommuting), used in physics to work on fermions, seem to be perfect for this purpose. Assume we have \(g_1,..., g_n\) Grassman variables: \(g_i g_j = - g_j g_i\) what also implies \(g_i g_i = 0\). So multiplication of \(n\) of such variables is nonzero iff it contains all indexes (vertices). Denote \(G = diag(g_i)\) as diagonal matrix made of these variables. It is now easy to see that: Graph \(A\) contains Hamilton cycle iff \(Tr((AG)^n) \neq 0 \). Grassman variables can be realized by matrices – so we could see this formula in terms of block matrices ... unfortunately known realizations require e.g. \(2^n\) size matrices, what is not helpful - we get only an implication: If P != NP, then there is no polynomial size matrix realization of Grassman variables. So probably these realizations just require exponentially large matrices, what seems reasonable. We could easily find \((AG)^{-1}\), so maybe there is a way to quickly find \((1-AG)^{-1}=\sum_{i=0}^n (AG)^i\), what should be sufficient? Any thoughts?
Multi-forum cut-and-paste: http://www.scienceforums.net/topic/83928-grassman-variables-for-hamilton-cycle-problem/ http://www.thescienceforum.com/physics/44818-grassman-variables-hamilton-cycle-problem.html "If P != NP, then there is no polynomial size matrix realization of Grassman [sic] variables" seems uninteresting to me because "there is no polynomial size realization of Grassmann variables" seems likely since \(\left( \prod_{i\in A} g_i \right) \left( \prod_{j\in B} g_j \right) = \left\{ \begin{array}{lcl} \pm \prod_{k\in A \cup B} g_k & \quad \quad \quad & \textrm{if} \quad A \cap B = \emptyset \\ 0 & & \textrm{otherwise} \end{array} \right.\) so in general we need a 2^n vector to represent a field extended by n Grassmann numbers. // Just remembered that you can't really use an index set, you need a sequence of indices to know the sign of the result, but it doesn't matter to the big picture (or if your field has two elements) so I tossed in an extra plus-minus sign to indicate that this calculation lacks enough details to find the sign if non-zero.
rpenner, indeed while these variables seem trivial when introducing for fermion systems, in fact their products have to "store" terms for all possible subsets (of fermions) - they hide exponentially large number of terms. But maybe this algebraic formulation of Hamilton cycle problem allows for some smarter approaches - like by inverting the matrix, or maybe using some fermionic path integral trick ... ?
