The symbolic pfaffian method I: A generalization of the Gallucio-Loebl-Tesler Theorem
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality