Counting graphic sequences via integrated random walks

Abstract

Given an integer $n$, let $G(n)$ be the number of integer sequences $n-1\ge d_1\ge d_2\ge \cdots \ge d_n\ge 0$ that are the degree sequence of some graph. We show that $G(n)=(c+o(1))4^n/n^{3/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-factors). Additionally, we answer a question of Royle, extend the values of $n$ for which the exact value of $G(n)$ is known from $n\le 290$ to $n\le 1651$ and determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative.

46 pages, 2 figures