Skip to main content

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

Export to calendar

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.