On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents

  • Anna Galluccio
  • Martin Loebl

Abstract

Kasteleyn stated that the generating function of the perfect matchings of a graph of genus $g$ may be written as a linear combination of $4^g$ Pfaffians. Here we prove this statement. As a consequence we present a combinatorial way to compute the permanent of a square matrix.

Published
1998-10-28
Article Number
R6