Abstract
In a recent article [Kawamoto, J. Phys. Complexity 4, 035005 (2023)], 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 this 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.
Original language | English |
---|---|
Article number | 093301 |
Number of pages | 14 |
Journal | Journal of Mathematical Physics |
Volume | 65 |
Issue number | 9 |
DOIs | |
Publication status | Published - 5 Sept 2024 |
Bibliographical note
Funding Information:We thank Tatsuro Kawamoto, Pawat Akara-pipattana, and especially Sergei Nechaev for valuable discussions about regular graph counting and related topics. O.E. is supported by Thailand NSRF via PMU-B, Grant No. B13F670063. W.H. is supported by the NSTDA of Thailand under the JSTP scholarship, Grant No. SCA-CO-2565-16992-TH.
Publisher Copyright:
© 2024 Author(s).