Analytic combinatorics of connected graphs
arXiv:1605.08597
Abstract
We enumerate the connected graphs that contain a number of edges growing linearly with respect to the number of vertices. So far, only the first term of the asymptotics and a bound on the error were known. Using analytic combinatorics, ie generating function manipulations, we derive a formula for the coefficients of the complete asymptotic expansion. The same result is derived for connected multigraphs.
38 pages + 22 pages of appendix, long version of the talk arXiv:1604.07307 accepted at FPSAC 2016