Nilpotent adjacency matrices, random graphs, and quantum random variables
Schott, René ; Staples, Stacey
HAL, hal-00136290 / Harvested from HAL
For fixed $n>0$, the space of finite graphs on $n$ vertices is canonically associated with an abelian, nilpotent-generated subalgebra of the $2n$-particle fermion algebra. using the generators of the subalgebra, an algebraic probability space of "nilpotent adjacency matrices" associated with finite graphs is defined. Each nilpotent adjacency matrix is a quantum random variable whose $m^th$ moment corresponds to the number of $m$-cycles in the graph $G$. Each matrix admits a canonical "quantum decomposition" into a sum of three algebraic random variables: $a = a^\Delta+ a^\Upsilon+a^Lambda$, where $a^\Delta$ is classical while $a^\Upsilon and $a^\Lambda$ are quantum. Moreover, within the algebraic context, the NP problem of cycle enumeration is reduced to matrix multiplication, requiring no more than $n^4$ multiplications within the algebra.
Publié le : 2008-07-05
Classification:  fermions,  random graphs,  cycles,  paths,  quantum computing,  60B99 ; 81P68 ; 05C38 ; 05C50 ; 05C80 ; 15A66,  [MATH.MATH-PR]Mathematics [math]/Probability [math.PR]
@article{hal-00136290,
     author = {Schott, Ren\'e and Staples, Stacey},
     title = {Nilpotent adjacency matrices, random graphs, and quantum random variables},
     journal = {HAL},
     volume = {2008},
     number = {0},
     year = {2008},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00136290}
}
Schott, René; Staples, Stacey. Nilpotent adjacency matrices, random graphs, and quantum random variables. HAL, Tome 2008 (2008) no. 0, . http://gdmltest.u-ga.fr/item/hal-00136290/