Serte Donderwinkel, McGill University
Authors: Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, Alex Scott
2023 AWM Research Symposium
Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]

A graphic sequence is a non-increasing sequence of natural numbers that can occur as the degree sequence of a graph. We show that the number of graphic sequences of length n grows like cn^{-3/4}4^n for some constant c. The foundation of our proof consists of a few reformulations, that turn our problem into a question about the lazy simple symmetric random walk bridge. To be precise, we calculate the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge never goes negative. Our reformulation also yields a new, efficient algorithm for exact enumeration of graphic sequences, with which we are able to calculate many more exact values than previously known. This talk is based on joint work with Paul Balister, Carla Groenland, Tom Johnston and Alex Scott.

Back to Search Research Symposium Abstracts