Nilpotent Adjacency Matrices and Random Graphs

Abstract

While powers of the adjacency matrix of a finite graph reveal information about walks on the graph, they fail to distinguish closed walks from cycles. Using elements of an appropriate commutative, nilpotent-generated algebra, a “new” adjacency matrix \(\Lambda\) can be associated with a random graph on \(n\) vertices. Letting \(X_k\) denote the number of \(k\)-cycles occurring in a random graph, this algebra together with a probability mapping allow \(\mathbb{E}(X_k)\) to be recovered in terms of \(\operatorname{tr} \Lambda^k\). Higher moments of \(X_k\) can also be computed, and conditions are given for the existence of higher moments in growing sequences of random graphs by considering infinite-dimensional algebras. The algebras used can be embedded in algebras of fermion creation and annihilation operators, thereby establishing connections with quantum computing and quantum probability theory. In the framework of quantum probability, the nilpotent adjacency matrix of a finite graph is a quantum random variable whose \(m\)th moment corresponds to the \(m\)-cycles contained in the graph.