2023/01/17 by Paul Balister, Serte Donderwinkel, Balister, Paul +7
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2301.07022
openalex publication_date 2023/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an integer n, let G(n) be the number of integer sequences n-1≥ d1≥ d2≥\dotsb≥ 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 the exact value of G(n) is known 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.