Stephan Wagner: Coefficients of graph polynomials associated with random trees and graphs
Time: Fri 2020-01-31 09.00 - 09.50
Location: Institut Mittag-Leffler, Seminar Hall Kuskvillan
Participating: Stephan Wagner, Uppsala University
Abstract
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ős-Rényi random graphs.