Tutte seminar - Chris Godsil

Friday, October 17, 2014 3:30 pm - 3:30 pm EDT (GMT -04:00)

The Matching Polynomial of a Graph

Speaker: Chris Godsil
Affiliation: University of Waterloo
Room: Mathematics 3 (M3) 3103

Abstract:

If  p(G,k) denotes the number of matchings of size k in the graph G and  n=|V(G)|, then the matching polynomial of G is

m(G,t) = \sum_k   p(G,k) (-1)^k t^{n-2k}.

Thus it is a form of generating function for the matchings in a graph. The matching polynomial was first used in physics and in chemistry; more recently it has featured in the construction of Ramanujan graphs
by Marcus et al. In my talk I will discuss some of the history of this polynomial, and some of its surprising properties.