Mathematical Sciences Research Institute

Home » Workshop » Schedules » An overview of the Matching Polynomial

An overview of the Matching Polynomial

Hot Topics: Kadison-Singer, Interlacing Polynomials, and Beyond March 09, 2015 - March 13, 2015

March 09, 2015 (03:30 PM PDT - 04:30 PM PDT)
Speaker(s): Chris Godsil (University of Waterloo)
Location: MSRI: Simons Auditorium


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.

Supplements No Notes/Supplements Uploaded
Video/Audio Files


H.264 Video 14180.mp4 263 MB video/mp4 rtsp://videos.msri.org/data/000/023/081/original/14180.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

See more of our Streaming videos on our main VMath - Streaming Video page.