Videos

An overview of the Matching Polynomial

Presenter
March 9, 2015
Keywords:
  • Marcus-Spielman-Srivastava theorem
  • generalizations of MSS
  • geometric algebra
  • Kadison-Singer theorem
  • algebraic combinatorics
MSC:
  • 68-xx
  • 68W25
  • 68Rxx
  • 11Cxx
  • 11C08
  • 46N10
  • 52Cxx
Abstract
A k-matching in a graph X is a set of k vertex-disjoint edges. If we denote the number of k-matchings in a graph G by p(G,k) and |V(G)|=n, then its matching polynomial is \[ \mu(G,t) = \sum_k (-1)^k p(G,k) t^{n-2k}. \] It is thus a form of generating function, with fudge factors inserted to make our work easier. Matchings are a central topic in graph theory, but nonetheless this polynomial appeared in Physics and in Chemistry, before becoming an object of interest to graph theorists. If the graph G is a forest, its matching polynomial coincides with the characteristic polynomial of the adjacency matrix of G, and considering the analogies between these two polynomials has proved very fruitful. In my talk I will present some of the history of the matching polynomial, along with interesting parts of its theory.