|
|
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.
|
|
|
|