Till innehåll på sidan

Stephan Wagner: Coefficients of graph polynomials associated with random trees and graphs

Tid: Fr 2020-01-31 kl 09.00 - 09.50

Plats: Institut Mittag-Leffler, Seminar Hall Kuskvillan

Medverkande: Stephan Wagner, Uppsala University

Exportera till kalender

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.