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\ge 1$, there exists a graph of orientable genus at most $g$ whose perfect-matching polynomial requires at least $(8\mathrm{/}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\mathrm{/}3{)}^{\lfloor n\mathrm{/}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.