- Series
- School of Mathematics Colloquium
- Time
- Thursday, October 16, 2025 - 11:00am for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Louigi Addario-Berry – McGill University – louigi.addario@mcgill.ca – https://problab.ca/louigi/
- Organizer
- Harold Blum, Xiaoyu He, Julia Lindberg, Rose McCarty, John McCuan, Dmitrii Ostrovskii, and Wei Zhu
Fix a finite set S of graphs, and let U be a uniformly random sample from S. We ask the question: what is the statistical behaviour of diam(U), the greatest graph distance between any two vertices in U? Many variants of this question have been asked, including for branching process trees (starting with the work of Kolmogorov 1938) and regular graphs (starting with the work of Bollobás 1982).
Two natural and very general settings for this question are when S has the form
S_1={T is a rooted tree with vertex set V(T)={1,...,n} and vertex degrees (d_1,...,d_n)}
or
S_2={G is a simple graph with vertex set V(G)={1,...,n} and vertex degrees (d_1,...,d_n)}
We explain how to answer such questions, and to prove tight diameter upper bounds, in both cases. One of the challenges in proving the results for S_2 is that in general we know neither how to approximately enumerate nor to efficiently sample from sets of the form S_2.
Time permitting, I may also discuss diameter lower bounds.
Based on joint works with Serte Donderwinkel, Gabriel Crudele, and Igor Kortchemski.