FKT algorithm

The FKT algorithm counts perfect matchings in planar graphs by computing the Pfaffian of a suitably signed adjacency matrix. Its key step is choosing edge signs so matching contributions do not cancel.

Connect

Pfaffian: A polynomial of a skew-symmetric matrix whose square equals its determinant. The algorithm’s signed adjacency matrix encodes the matching count in this polynomial.
Petr Kasteleyn: A Dutch physicist who developed Pfaffian methods for counting dimers on planar lattices. His work established a central signing method behind the algorithm.
Aztec diamond: A family of lattice regions whose domino tilings have an exact enumeration formula. Its tilings provide a celebrated setting for applying planar dimer counting.
Valiant's theorem: The theorem that counting perfect matchings in general graphs is #P-complete. It highlights why the FKT algorithm’s planar restriction makes its polynomial-time result exceptional.
Kasteleyn orientation: An orientation of a planar graph’s edges satisfying a parity condition on every face. It provides a standard way to sign edges so all perfect matchings contribute consistently.
Harold N. V. Temperley: A British mathematician who studied domino tilings and their relation to spanning trees. His work helped connect planar matching counts with determinant-based methods.
Monomer-dimer model: A lattice model allowing both occupied edges, called dimers, and uncovered vertices, called monomers. The FKT method handles the perfect-matching case that underlies this broader model.
Bipartite adjacency matrix: A matrix recording edges between the two vertex classes of a bipartite graph. For bipartite planar graphs, a signed determinant can count matchings instead of a Pfaffian.
Skew-symmetric matrix: A square matrix equal to the negative of its transpose. The signed adjacency matrix used for the Pfaffian has this structure.
Michael E. Fisher: A physicist known for contributions to statistical mechanics and critical phenomena. His work with Temperley helped frame planar dimer enumeration as a statistical-mechanics problem.