Coefficients of graph polynomials associated with random trees and graphs

Algebraic and Enumerative Combinatorics

31 January 09:00 - 09:50

Stephan Wagner - Uppsala University

There are many polynomials associated with graphs whose coefficients count substructures of different kinds. Examples include the matching polynomial (matchings), the independence polynomial (independent sets), the subtree polynomial (subtrees) and the characteristic polynomial of the Laplacian (rooted spanning forests). In this talk, I will discuss the distribution of these coefficients in different families of random trees and graphs. One can prove limit laws for the coefficients of a variety of graph polynomials under different random models (and even in some deterministic cases). To give just one concrete example: the coefficients of the subtree polynomial asymptotically follow a normal distribution when uniformly random trees are considered, but a Poisson distribution for dense Erd\H{o}s-R\'enyi random graphs.
Sara Billey
University of Washington
Petter Brändén
KTH Royal Institute of Technology
Sylvie Corteel
Université Paris Diderot, Paris 7
Svante Linusson
KTH Royal Institute of Technology


Svante Linusson


For practical matters at the Institute, send an e-mail to