Abstract: A perfect matching of a graph $G=(V,E)$ is a covering set of matchings $\mu\subseteq E$ such that every vertex of $G$ is contained in exactly one edge $e\in \mu$. The number of perfect matchings for a given graph and its asymptotics show connections to various other areas of science including electrostatics, statistical mechanics and chemistry. From mathematical and especially combinatorial point of view, perfect matching enumeration is a highly multi-facetted problem whose complexity is heavily influenced by the structure of the underlying graph. A first successful attempt to give a general solution was achieved by Kasteleyn in the 1960s. By assigning a certain orientation on the edges of $G$ he was able to express the perfect matching generating function $M(G)$ of any PLANAR graph $G$ as plus or minus a Pfaffian form of its skew-symmetric adjacency matrix. After a brief introduction to the theory of Pfaffian forms, we will study Kasteleyn's method together and use the strong correspondence between perfect matchings and Pfaffians to directly translate identities of Pfaffian forms into formulas for perfect matchings. Extending the work of Markus Fulmek (2010) this provides an algebraic approach to proving condensation formulas for perfect matchings as an alternative to the purely combinatorial method. While Fulmek used involutions on superposition cycles to translate Pfaffian formulas into the language of perfect matchings, we will take the slightly more technical path by explicitly deducing the translation signs of the respective Pfaffians, which allows us to translate formulas of higher degree even where the involution-approach is no longer applicable. In the end, if time allows, we mention the complications that occur when poking holes of odd size into our planar graph. We explore a possible solution to this problem by connecting holes of odd size to larger holes of even size via certain well-behaved paths.
Perfect matching enumeration and Kasteleyn‘s method
10.06.2025 15:15 - 16:45
Organiser:
Z. Salvy
Location: