Math 2.0

Combinatorics Theorem

FKT algorithm

Builds on Planar graphPerfect matchingPfaffianSkew-symmetric matrix

Statement

Let G=(V,E)G = (V, E) be a finite graph with vertex set V={1,…,2n}V = \set{1, \dots, 2n}. Fix an orientation G⃗\vec{G} of its edges. Let AA be the 2n×2n2n \times 2n skew-symmetric matrix with Auv=1A_{uv} = 1 if u→vu \to v, Auv=−1A_{uv} = -1 if v→uv \to u, and Auv=0A_{uv} = 0 otherwise. The orientation is Pfaffian if all perfect matchings of GG contribute with the same sign to the Pfaffian Pf(A)\mathrm{Pf}(A). Then ∣Pf(A)∣\abs{\mathrm{Pf}(A)} is the number of perfect matchings of GG.

If GG is planar, then:

  1. GG has a Pfaffian orientation, and the number of perfect matchings of GG equals ∣Pf(A)∣=det⁡A\abs{\mathrm{Pf}(A)} = \sqrt{\det A}.
  2. Such an orientation can be found, and the number of perfect matchings computed, in time polynomial in ∣V∣\abs{V}.

Remarks

The Pfaffian expands as a signed sum over perfect matchings. The symmetric difference of two matchings is a union of disjoint even cycles, and the orientations around these cycles govern their relative sign. Kasteleyn's condition is that, in a planar embedding, every bounded face has an odd number of edges oriented clockwise along its boundary; this forces all signs to agree. The algorithm takes a spanning tree and orients its edges arbitrarily. It then orients the remaining edges one at a time, in an order given by a spanning tree of the dual graph. Each such edge closes a face, and its direction is chosen to fix the parity of that face. The determinant is computed by Gaussian elimination in polynomial time. With positive edge weights placed in AA instead of ±1\pm 1, the same method computes the partition function of the dimer model. Planarity cannot be dropped in general: counting perfect matchings of general graphs is #P-complete by Valiant's theorem.

Going deeper

For a student

The result is named after Fisher, Kasteleyn and Temperley, who found it in the early 1960s to count dimer coverings and domino tilings. It shows the gap between the permanent, which counts matchings and is hard, and the determinant, which is easy. It extends to graphs of bounded genus with a sum of several Pfaffians, and it underlies the exact solution of the planar Ising model through a dimer representation.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph
Perfect matching, concept, no evidence levelPerfect matchingconceptPfaffian, concept, no evidence levelPfaffianconceptPlanar graph, concept, no evidence levelPlanar graphconceptSkew-symmetric matrix, concept, no evidence levelSkew-symmetric matrixconceptFKT algorithm, statement, no evidence levelFKT algorithmstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Perfect matching concept
  2. Pfaffian concept
  3. Planar graph concept
  4. Skew-symmetric matrix concept
  5. FKT algorithm statement

Further reading

  1. Web https://en.wikipedia.org/wiki/FKT_algorithm
About this page
TagA6SPEDH8BK
URIm2://A6SPEDH8BK
Kindstatement, theorem
WritingW0 stub
MSC05C70, 05C85, 82B20
StatusThis copy of the site has no build data. Run m2 status A6SPEDH8BK.
AboutPerfect matching, Pfaffian
UsesPlanar graph, Perfect matching, Pfaffian, Skew-symmetric matrix
Same as
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.