The symbolic pfaffian method I: A generalization of the Gallucio-Loebl-Tesler Theorem

arXiv:2611.00468 · math.CO, cs.DM · Submitted 2026-10-30 · Read on arXiv

math.CO, cs.DM

Submitted: 2026-10-30

Updated: 2026-10-30

Comments: 20 pages, 3 figures

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

The gist: The pfaffian number of a graph G, denoted by pf(G), is the minimum integer k such that the generating function of perfect matchings of G can be written as a linear combination of k pfaffians of…

Terminology

Abstract

The pfaffian number of a graph G, denoted by pf(G), is the minimum integer k such that the generating function of perfect matchings of G can be written as a linear combination of k pfaffians of signed adjacency matrices. The Galluccio-Loebl-Tesler Theorem states that pf(G) at most 4 g, where g is the orientable genus of G. We generalize this theorem by relating the pfaffian number of a graph to another graph parameter: the symbolic pfaffian number, denoted by spf(G). Namely, we prove that pf(G) at most 2 spf(G). Our proof is based on linear algebra arguments and does not depend on topological properties of graphs. As a consequence of our generalization, we conclude that pf(K 2n) = 2 O(n n), an improvement on the previous upper bound of 4 O(n 2) based on the genus. We also consider lower bounds for pf(G) related to spf(G). In particular, we show that the graphs with pf(G) = 4 are the graphs with spf(G) = 2. On the other hand, we show that our main result is strictly more general than a previous generalization by Norine.

Sources

Related papers