Exponential Lower Bounds for the Pfaffian Number of Graphs

The Fisher--Kasteleyn--Temperley (FKT) algorithm counts perfect matchings in planar graphs in polynomial time using a single Pfaffian computation.

Galluccio--Loebl and Tesler extended this Pfaffian method to graphs embedded in an orientable surface of genus $g$, showing that the perfect-matching polynomial can be written as a linear combination of at most $4^g$ Pfaffians.

We prove that this exponential dependence on $g$ is unavoidable in general.

More precisely, for every $g\ge1$, there exists a graph of orientable genus at most $g$ whose perfect-matching polynomial requires at least $(8/3)^g$ Pfaffians in any such linear representation.

In particular, for every even integer $n\ge 6$, there is a graph on $n$ vertices with Pfaffian number at least $(8/3)^{\lfloor n/6\rfloor}$.

Moreover, the lower bound is witnessed even by connected cubic bipartite matching-covered graphs of orientable genus exactly $g$.

We also prove exponential lower bounds for complete bipartite graphs, and hence for even complete graphs, improving asymptotically on a recent linear lower bound of Junchaya, Miranda, and Lucchesi.