Notices
Results 1 to 1 of 1

Thread: Grassman variables for Hamilton cycle problem?

  1. #1 Grassman variables for Hamilton cycle problem? 
    Forum Junior
    Join Date
    Jul 2008
    Posts
    287
    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 and its number of vertices by , diagonal elements of 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 Grassman variables: what also implies . So multiplication of of such variables is nonzero iff it contains all indexes (vertices).
    Denote as diagonal matrix made of these variables. It is now easy to see that:

    Graph contains Hamilton cycle iff .

    Grassman variables can be realized by matrices so we could see this formula in terms of block matrices ... unfortunately known realizations require e.g. 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 , so maybe there is a way to quickly find , what should be sufficient?

    Any thoughts?


    Reply With Quote  
     

  2.  
     

Similar Threads

  1. Replies: 1
    Last Post: August 31st, 2012, 03:45 PM
  2. Batteries cycle life problem
    By Stanley514 in forum Chemistry
    Replies: 2
    Last Post: April 15th, 2011, 11:55 AM
  3. Dependent and Independent Variables.
    By Ekechukwu in forum Chemistry
    Replies: 4
    Last Post: May 21st, 2010, 11:17 PM
  4. complex variables
    By Arcane_Mathematician in forum Mathematics
    Replies: 9
    Last Post: June 14th, 2009, 10:54 PM
  5. problems with variables
    By vindicated in forum Chemistry
    Replies: 1
    Last Post: August 9th, 2006, 04:05 AM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •