Discrete Mathematics and Optimization Seminar
Apr. 20, 2009
A Continuous-Discrete Symbiosis: Counting Matchings with Integrals
Mark Kayll
University of Montana
How many perfect matchings are contained in a given bipartite graph? An exercise in Godsilís 1993 Algebraic Combinatorics solicits proof that this ques- tioní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 indepen- dently 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.