Back to Search
Start Over
Counting graphic sequences via integrated random walks
- Publication Year :
- 2023
-
Abstract
- Given an integer $n$, let $G(n)$ be the number of integer sequences $n-1\ge d_1\ge d_2\ge\dotsb\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\le290$ to $n\le 1651$ and determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative.<br />Comment: 46 pages, 2 figures
- Subjects :
- Mathematics - Combinatorics
Mathematics - Probability
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2301.07022
- Document Type :
- Working Paper