Connected components and evolution of random graphs: An algebraic approach

摘要

Questions about a graph's connected components are answered by studying appropriate powers of a special "adjacency matrix" constructed with entries in a commutative algebra whose generators are idempotent. The approach is then applied to the Erd?s-Rényi model of sequences of random graphs. Developed herein is a method of encoding the relevant information from graph processes into a "second quantization" operator and using tools of quantum probability and infinite-dimensional analysis to derive formulas that reveal the exact values of quantities that otherwise can only be approximated. In particular, the expected size of a maximal connected component, the probability of existence of a component of particular size, and the expected number of spanning trees in a random graph are obtained.