A Gaussian integral that counts regular graphs
arXiv:2403.04242 · doi:10.1063/5.0208715
Abstract
In a recent article J. Phys. Compl. 4 (2023) 035005, Kawamoto evoked statistical physics methods for the problem of counting graphs with a prescribed degree sequence. This treatment involved truncating a particular Taylor expansion at the first two terms, which resulted in the Bender-Canfield estimate for the graph counts. This is surprisingly successful since the Bender-Canfield formula is asymptotically accurate for large graphs, while the series truncation does not a priori suggest a similar level of accuracy. We upgrade the above treatment in three directions. First, we derive an exact formula for counting d-regular graphs in terms of a d-dimensional Gaussian integral. Second, we show how to convert this formula into an integral representation for the generating function of d-regular graph counts. Third, we perform explicit saddle point analysis for large graph sizes and identify the saddle point configurations responsible for graph count estimates. In these saddle point configurations, only two of the integration variables condense to significant values, while the remaining ones approach zero for large graphs. This provides an underlying picture that justifies Kawamoto's earlier findings.
arXiv commentv2: typos corrected, references added, accepted for publication
References in corpus (25)
- Quantum Field Theory in the Large N Limit: a review
- Entropy measures for complex networks: Toward an information theory of complex topologies
- The entropy of network ensembles
- The entropy of randomized network ensembles
- Solution of the 2-star model of a network
- Spectra of Euclidean Random Matrices
- Spectra of Sparse Random Matrices
- Return probability for the Anderson model on the random regular graph
- Network Transitivity and Matrix Models
- Entropies of complex networks with hierarchically constrained topologies
- The Ising Model on Random Lattices in Arbitrary Dimensions
- Finite size correction to the spectrum of regular random graphs: an analytical solution
- Analytical results for the distribution of first return times of random walks on random regular graphs
- Distribution of shortest cycle lengths in random networks
- The two-star model: exact solution in the sparse regime and condensation transition
- Random matrices with row constraints and eigenvalue distributions of graph Laplacians
- Exact Free Energies of Statistical Systems on Random Networks
- Ising model on random networks and the canonical tensor model
- Analytical results for the distribution of cover times of random walks on random regular graphs
- The mean and variance of the distribution of shortest path lengths of random regular graphs
- Analytical results for the distribution of first hitting times of random walks on random regular graphs
- Entropy of labeled versus unlabeled networks
- Analytical results for the distribution of first-passage times of random walks on random regular graphs
- Automatic enumeration of regular objects
- Entropy of microcanonical finite-graph ensembles