Asymptotic enumeration of graph factors by cumulant expansion
Preprint
Abstract
Let $G$ be a dense graph with good expansion properties and not too close to being bipartite. Let $\boldsymbol d$ be a graphical degree sequence. Under very weak conditions, we find the number of subgraphs of $G$ with degree sequence $\boldsymbol d$ to arbitrary precision. The average degree can be any power of $n$ and the variation in degrees can be very large. The method uses an explicit bound on the tail of the cumulant generating function found by the first author. As a first application, we prove that there is an asymptotic expansion for the number of regular graphs and find several terms explicitly. We believe that this is the first combinatorial application of the Fourier inversion method for which the integral outside the dominant regions cannot be bounded by the integral of the absolute value, and we give a general method for dealing with that situation.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Cumulant expansion for counting Eulerian orientationsJournal of Combinatorial Theory, Series B, 2025
- Enumeration of graphs with a heavy-tailed degree sequenceAdvances in Mathematics, 2016
- Practical graph isomorphism, IIJournal of Symbolic Computation, 2014
- Bipartiteness and the least eigenvalue of signless Laplacian of graphsLinear Algebra and its Applications, 2012
- The number of graphs and a random graph with a given degree sequenceRandom Structures & Algorithms, 2012
- Asymptotic enumeration by degree sequence of graphs with degreeso(n 1/2)Combinatorica, 1991
- The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphsCombinatorica, 1990
- Asymptotic Enumeration by Degree Sequence of Graphs of High DegreeEuropean Journal of Combinatorics, 1990
- The number of matchings in random regular graphs and bipartite graphsJournal of Combinatorial Theory, Series B, 1986
- The asymptotic number of labeled graphs with given degree sequencesJournal of Combinatorial Theory, Series A, 1978