Hamiltonian cycle enumeration via fermion-zeon convolution

All code by G. Stacey Staples except as indicated.

(* Generate adjacency matrix of homogeneous random graph on n vertices.  Undirected, no multiple edges.  Each pair of vertices has probability p of being adjacent. *)
GenRandGraph[n_,p_]:=Module[{i,j,A,rw,co},A=Table[0,{i,1,n},{j,1,n}];For[rw=1,rw≤n,rw++,For[co=1,co<rw,co++,If[RandomReal[]<p,A[[rw,co]]=1;A[[co,rw]]=1;,Null];]];Return[A]];

(* Generate random directed graph on n vertices. *)GenRandDirGraph[n_,p_]:=Table[If[Random[]≤p,1,0],{i,1,n},{j,1,n}];

(* Digraph example *)
n=12;A=GenRandDirGraph[n,.4];
GraphPlot[A,DirectedEdges->True]

(* Implementation of matrix permanent by Eric W. Weisstein, 2004.  Notebook available at 
http://mathworld.wolfram.com/notebooks/LinearAlgebra/Permanent.nb *)
Permanent[m_List]:=With[{v=Array[x,Length[m]]},Coefficient[Times@@(m.v),Times@@v]]

Considering the adjacency matrix A as an operator on R^n, let A induce operators ϕ and ξ on fermion and zeon algebras, respectively.

FermionInduced[A_, lvl_]:=Module[{S,i,j},
If[lvl==0,{{1}},S=Subsets[Range[Length[A]],{lvl}];
Table[Det[A[[i,j]]],{i,S},{j,S}]]];

ZeonInduced[A_, lvl_]:=Module[{S,i,j},
If[lvl==0,{{1}},S=Subsets[Range[Length[A]],{lvl}];
Table[Permanent[A[[i,j]]],{i,S},{j,S}]]];

Define diagonal operator σ on fermion Fock space as follows.

SigmaMat[n_]:=Module[{S,j},S=Subsets[Range[n]];
DiagonalMatrix[Table[(((-1))^(Length[j]))(n-Length[j]),{j,S}]]]

Hamiltonian cycles are enumerated by fermion-zeon convolution: (Subscript[H, c]) = ∫(σϕ*ξ)dγdζ, 
as described in the preprint Graph-induced operators: Hamiltonian cycle enumeration via fermion-zeon convolution by G. Stacey Staples, 2014.  Available at
https://dl.dropboxusercontent.com/u/92994077/FermionZeonTrace20140701.pdf

The star dual of the induced zeon operator used in the convolution can be computed explicitly using the following procedure.

ZeonConvDual[A_,k_]:=Reverse[Transpose[Reverse[ZeonInduced[A,Length[A]-k]]]];

FZConvolution handles all aspects of computing the convolution.

FZConvolution[A_]:=Sum[(((-1))^k)(Length[A]-k)Tr[ FermionInduced[A,k] Reverse[Transpose[Reverse[ZeonInduced[A,Length[A]-k]]]]],{k,0,Length[A]}]

The following code generates random graphs and counts the Hamiltonian cycles by applying fermion-zeon convolution.  The implementation can be made significantly faster by eliminating the explicit computations of the induced operators.

For[lp=1,lp≤10,lp++,
A=GenRandGraph[8,.5];
Print[GraphPlot[A]];

Print["(Subscript[H, c]) = ∫(σϕ*ξ)dγdζ = ",FZConvolution[A]/(Length[A])]]