Exponential Lower Bounds for the Pfaffian Number of Graphs
For researchers in graph theory and computational complexity, this provides a tight exponential lower bound on the Pfaffian number, showing that the known upper bound is essentially optimal.
The paper proves that exponentially many Pfaffians are needed to express the perfect-matching polynomial of graphs on orientable surfaces of genus g, with a lower bound of (8/3)^g, improving on previous upper bounds of 4^g. It also obtains exponential lower bounds for complete bipartite graphs, improving on a recent linear bound.
Galluccio--Loebl and Tesler showed that the perfect-matching polynomial of a graph embedded in an orientable surface of genus $g$ can be written as a linear combination of at most $4^g$ Pfaffians. We show that, in general, exponentially many Pfaffians are necessary. More precisely, among all graphs of orientable genus at most $g$, the maximum possible Pfaffian number is at least $(8/3)^g$. This lower bound holds even for connected matching-covered graphs. We also obtain exponential lower bounds for the Pfaffian number of complete bipartite graphs, and hence for even complete graphs, improving asymptotically on a recent linear lower bound of Junchaya, Lucchesi, and Miranda.