Counting graphic sequences via integrated random walks

Paul Balister; Serte Donderwinkel; Carla Groenland; Tom Johnston; Alex Scott

doi:10.1090/tran/9403

Counting graphic sequences via integrated random walks

Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, Alex Scott

Discrete Mathematics and Optimization

Research output: Contribution to journal › Article › Scientific › peer-review

3 Downloads (Pure)

Abstract

Given an integer n, let G(n) be the number of integer sequences n − 1 ≥ d₁ ≥ d₂ ≥ · · · ≥ d_n ≥ 0 that are the degree sequence of some graph. We show that G(n) = (c + o(1))4ⁿ/n³/⁴ for some constant c > 0, improving both the previously best upper and lower bounds by a factor of n¹/⁴ (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.

Original language	English
Pages (from-to)	4627-4669
Number of pages	43
Journal	Transactions of the American Mathematical Society
Volume	378
Issue number	7
DOIs	https://doi.org/10.1090/tran/9403
Publication status	Published - 2025

Bibliographical note

Green Open Access added to TU Delft Institutional Repository as part of the Taverne amendment. More information about this copyright law amendment can be found at https://www.openaccess.nl. Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Access to Document

10.1090/tran/9403

tran9403

Cite this

@article{e96e47877f1647ce922062b72e79d794,

title = "Counting graphic sequences via integrated random walks",

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.",

author = "Paul Balister and Serte Donderwinkel and Carla Groenland and Tom Johnston and Alex Scott",

note = "Green Open Access added to TU Delft Institutional Repository as part of the Taverne amendment. More information about this copyright law amendment can be found at https://www.openaccess.nl. Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. ",

year = "2025",

doi = "10.1090/tran/9403",

language = "English",

volume = "378",

pages = "4627--4669",

journal = "Transactions of the American Mathematical Society",

issn = "0002-9947",

publisher = "American Mathematical Society",

number = "7",

}

TY - JOUR

T1 - Counting graphic sequences via integrated random walks

AU - Balister, Paul

AU - Donderwinkel, Serte

AU - Groenland, Carla

AU - Johnston, Tom

AU - Scott, Alex

N1 - Green Open Access added to TU Delft Institutional Repository as part of the Taverne amendment. More information about this copyright law amendment can be found at https://www.openaccess.nl. Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=105008552431&partnerID=8YFLogxK

U2 - 10.1090/tran/9403

DO - 10.1090/tran/9403

M3 - Article

AN - SCOPUS:105008552431

SN - 0002-9947

VL - 378

SP - 4627

EP - 4669

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

IS - 7

ER -

Counting graphic sequences via integrated random walks

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this