A Gaussian integral that counts regular graphs

Oleg Evnin, Weerawit Horinouchi

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
5 Downloads (Pure)

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 languageEnglish
Article number093301
Number of pages14
JournalJournal of Mathematical Physics
Volume65
Issue number9
DOIs
Publication statusPublished - 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).

Cite this