All Title Author
Keywords Abstract

Another short proof of the Joni-Rota-Godsil integral formula for counting bipartite matchings

Full-Text   Cite this paper   Add to My Lib


How many perfect matchings are contained in a given bipartite graph? An exercise in Godsil's 1993 extit{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 extit{An Introduction to Combinatorial Analysis}. It was stated more explicitly and proved independently by S.A.~Joni and G.-C.~Rota [ extit{JCTA} extbf{29} (1980), 59--73] and C.D.~Godsil [ extit{Combinatorica} extbf{1} (1981), 257--262]. Another generation later, perhaps it's time both to simplify the proof and to broaden the formula's reach.


comments powered by Disqus