Asymptotic enumeration of graph factors by cumulant expansion
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908503936860160 |
|---|---|
| author | Isaev, Mikhail McKay, Brendan D. |
| author_facet | Isaev, Mikhail McKay, Brendan D. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18731 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic enumeration of graph factors by cumulant expansion Isaev, Mikhail McKay, Brendan D. Combinatorics 05C30, 05A16, 05C80 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. |
| title | Asymptotic enumeration of graph factors by cumulant expansion |
| topic | Combinatorics 05C30, 05A16, 05C80 |
| url | https://arxiv.org/abs/2508.18731 |