Affiliation: University of British Columbia, Canada
Title: Deletion-contraction for a unified Laplacian and applications
Abstract: We define a graph Laplacian with vertex weights in addition to the more classical edge weights, which unifies the combinatorial Laplacian and the normalised Laplacian. Moreover, we give a combinatorial interpretation for the coefficients of the weighted Laplacian characteristic polynomial in terms of weighted spanning forests and use this to prove a deletion-contraction relation. We will see applications to some of: eigenvalue interlacing theorems, sparse cuts, independent sets, proper colourings, constructing cospectral graphs and isomorphism problems in graph theory. Joint work with Farid Aliniaeifard and Steph van Willigenburg.
You can watch the talk here.
This talk was given on April 11th, 2022