Counting graphic sequences via integrated random walks
Given an integer n, let G(n) be the number of integer sequences n − 1 ≥ d1 ≥ d2 ≥ · · · ≥ dn ≥ 0 that are the degree sequence of some graph. We show that G(n) = (c + o(1))4n/n3/4 for some constant c > 0, improving both the previously best upper and lower bounds by a factor of n 1/4 (up to polylog...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
American Mathematical Society
2024
|