Counting graphic sequences via integrated random walks
Paul Balister (University of Oxford)
Serte Donderwinkel (University Medical Center Groningen)
Carla Groenland (TU Delft - Discrete Mathematics and Optimization)
Tom Johnston (University of Bristol)
Alex Scott (University of Oxford)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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 n1/4 (up to polylog-factors). Additionally, we answer a question of Royle, extend the values of n for which G(n) is known exactly from n ≤ 290 to n ≤ 1651 and determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative.