Nilpotent adjacency matrices and random graphs. (Q2881260)

Given the adjacency matrix \(A = A(G)\) of a graph \(G\), for \(k \geq 1\), \(A^k\) represents the number of walks with \(k\) edges between pairs of vertices, and the trace \(tr(G)\) is the total number of closed walks with \(k\) edges. A nilpotent adjacency matrix \(\Lambda = \Lambda (G)\) is defined with entries from an appropriately defined abelian nilpotent-generated algebra \(\mathcal {N}\). The matrix \(\Lambda ^k\) can be used to determine the number of cycles (closed walks without duplicated vertices) in the graph \(G\), and in fact this information comes from the trace \(\text{tr}(\Lambda ^k)\). If \(X_k\) is the random variable of the number of cycles of length \(k\) in a random graph \(G\), then the expected value \(E(X_k)\) can be computed using the \(\text{tr}(\Lambda ^k(G))\), and also higher degree moments, such as the variance, can be computed using \(\Lambda ^k\).