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

  • Anna Galluccio
  • Martin Loebl
DOI: https://doi.org/10.37236/1438

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
Issue
Volume 6 (1999)
Article Number
R6