Exponential Lower Bounds for the Pfaffian Number of Graphs
Abstract
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 4g Pfaffians. We show that, in general, exponentially many Pfaffians are necessary. More precisely, for every g≥1, 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≥6, there is a graph on n vertices with Pfaffian number at least (8/3)⌊ n/6⌋. Moreover, the lower bound is witnessed even by cubic bipartite matching-covered graphs. We prove this by showing that expressing the permanent of an n× n matrix of distinct variables as a linear combination of determinants obtained by changing signs of its entries requires exponentially many determinants. As a consequence, we improve a recent linear lower bound on the Pfaffian number due to Junchaya, Miranda, and Lucchesi to an exponential lower bound.
Related
- Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries
- Localization Lengths for Two-Dimensional Random Band Matrices: Stretched-Exponential Lower Bounds
- Explicit lower bounds on the conductors of elliptic curves and abelian varieties over number fields
- The Maximum Number of Halving Lines for Finite Planar Sets—New Lower Bounds
- A characterization of graphs attaining a lower bound on the dissociation number
BibTeX
@misc{pant2026exponential,
title = {{Exponential Lower Bounds for the Pfaffian Number of Graphs}},
author = {Priyanshu Pant and Ranveer Singh},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.21077},
eprint = {2605.21077},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.21077},
}
RIS
TY - UNPB
TI - Exponential Lower Bounds for the Pfaffian Number of Graphs
AU - Priyanshu Pant
AU - Ranveer Singh
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2605.21077
UR - https://arxiv.org/abs/2605.21077
AB - 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, for every g≥1, 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≥6, there is a graph on n vertices with Pfaffian number at least (8/3)^⌊ n/6⌋. Moreover, the lower bound is witnessed even by cubic bipartite matching-covered graphs. We prove this by showing that expressing the permanent of an n× n matrix of distinct variables as a linear combination of determinants obtained by changing signs of its entries requires exponentially many determinants. As a consequence, we improve a recent linear lower bound on the Pfaffian number due to Junchaya, Miranda, and Lucchesi to an exponential lower bound.
ER -