Seminar

Zoom Link

A score sequence is a non-increasing sequence of natural numbers that can occur as an out-degree sequence of an orientation of the complete graph (i.e. as the scores in a round-robin tournament). The first estimates on the number of score sequences of length n are due to Erdös and Moser. With Brett Kolesnik, we resolve their conjecture and show that this number grows like cn^{-5/2}4^n. The foundation of our proof consists of some reformulations that turn our problem into a question about the persistence probability of the area process of the simple symmetric random walk bridge. We also obtain a Brownian scaling limit of a uniformly random score sequence.

In the second part of the talk, I will also touch upon an earlier, related work with Paul Balister, Carla Groenland, Tom Johnston and Alex Scott, where we use random walk techniques to asymptotically enumerate the number of non-increasing sequences that can occur as the degree sequence of a graph, answering a question by Royle. The techniques in this work inspired the work with Kolesnik.

Counting score sequences (and graphic sequences) via random walks