Nilpotent adjacency matrices and random graphs.
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\).
- A new adjacency matrix for finite graphs
- Zeon and idem-Clifford formulations of Boolean satisfiability
- Generalized zeon algebras: theory and application to multi-constrained path problems
- Spinorial formulations of graph problems
- Nilpotent adjacency matrices, random graphs and quantum random variables
- Connected components and evolution of random graphs: An algebraic approach
- Complexity of counting cycles using zeons
This page was built for publication: Nilpotent adjacency matrices and random graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2881260)
