Ottawa–Carleton
Discrete Mathematics Group

3 April 2009, 11.30am
HP4351, Carleton

How many perfect matchings are contained in a given bipartite graph? An exercise in Godsil's 1993 Algebraic Combinatorics solicits proof that this question's answer is an integral involving a certain rook polynomial. Though not widely known, this result appears implicitly in Riordan's 1958 An Introduction to Combinatorial Analysis. It was stated more explicitly and proved independently by S.A. Joni and G.-C. Rota [JCTA 29 (1980), 59–73] and C.D. Godsil [Combinatorica 1 (1981), 257–262]. Another generation later, perhaps it's time both to simplify the proof and to broaden the formula's reach. I'll present a self-contained proof and a delightful application. This talk is based on joint work with Erin Emerson.