Order statistics for vertex degrees in random unlabeled trees

Konstantinos Panagiotou (LMU)

Oct 19. 2026, 15:45 — 16:45

Let U_n be an unlabeled tree, drawn uniformly at random from the set of all unlabeled trees with n vertices. We establish that the maximum degree of U_n is, in total variation distance, very close to the maximum of c*n iid geometric random variables with parameter p, where c and p are explicitly given. Moreover, the second largest, the third largest, ..., degrees behave like the respective order statistics of the same geometric random variables, also jointly. Our method is flexible enough to accommodate other distributions, for example random unlabeled trees with degree restrictions.

 

Further Information
Venue:
ESI Boltzmann Lecture Hall
Associated Event:
Statistical Mechanics and Combinatorics of Discrete Planar Structures (Thematic Programme)
Organizer(s):
Nathanael Berestycki (U of Vienna)
Michael Drmota (TU Wien)
Ilse Fischer (U of Vienna)
Mihyun Kang (TU Graz)
Astrid Kollros (U of Vienna)
Christian Krattenthaler (U of Vienna)
Marcin Lis (TU Wien)
Benedikt Stufler (TU Wien)
Fabio Toninelli (TU Wien)