{"id":"arxiv/2605.21077","url":"https://arxiv.org/abs/2605.21077","tags":["math.CO","cs.DM"],"score":0,"title":"Exponential Lower Bounds for the Pfaffian Number of Graphs","domain":"math.CO","source":"arxiv","authors":["Priyanshu Pant","Ranveer Singh"],"reviews":0,"subject":"math.CO","summary":"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\\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\\ge6$, there is a graph on $n$ vertices with Pfaffian number at least $(8/3)^{\\lfloor…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-20","reactions":{}}