Counting graphic sequences
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.
Date:
10 May 2023, 11:00 (Wednesday, 3rd week, Trinity 2023)
Venue:
Mathematical Institute, Woodstock Road OX2 6GG
Venue Details:
L4
Speaker:
Serte Donderwinkel (McGill University)
Organising department:
Department of Statistics
Part of:
Probability seminar
Booking required?:
Not required
Audience:
Public
Editors:
Christina Goldschmidt,
James Martin
