Vortrag
Counting graphic sequences (and score sequences) via random walks
Vortrag von Prof. Dr. Serte Donderwinkel
Datum: 29.05.24 Zeit: 17.15 - 18.45 Raum: ETH HG G 43
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, answering a question by Royle. 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. In the last part of the talk, I will also touch upon a work with Brett Kolesnik, in which we use random walk techniques to show that the possible (non-increasing) score sequences of a round-robin tournament with n players grows like c'n^{-5/2}4^n for some constant c', answering a question by Erdös and Moser. We also obtain a Brownian scaling limit of a uniformly random score sequence.