Graph pfaffian number bounded by symbolic pfaffian number with new linear algebra proof

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

Discrete Mathematics

Summary

Graphs can be analyzed by looking at their perfect matchings, which are ways to pair up all the points without overlap. The pfaffian number measures how complicated it is to describe these matchings using a special mathematical tool called pfaffians. The authors found a new way to link this number to another measure, called the symbolic pfaffian number, with a proof that uses only linear algebra and no complex geometry. This approach improves our understanding and gives better upper bounds on this measurement for certain graphs, including complete graphs. They also clarified cases where small pfaffian numbers occur and showed their result is more general than previous work.

What this means in practice

A theory result. No direct application yet.

Authors

Enrique Junchaya, Cláudio L. Lucchesi, Alberto A. A. Miranda

Abstract

The pfaffian number of a graph $G$, denoted by $\mathrm{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 $\mathrm{pf}(G) \leq 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 $\mathrm{spf}(G)$. Namely, we prove that $\mathrm{pf}(G) \leq 2^{\mathrm{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 $\mathrm{pf}(K_{2n}) = 2^{\mathcal{O}(n \log n)}$, an improvement on the previous upper bound of $4^{\mathcal{O}(n^2)}$ based on the genus. We also consider lower bounds for $\mathrm{pf}(G)$ related to $\mathrm{spf}(G)$. In particular, we show that the graphs with $\mathrm{pf}(G) = 4$ are the graphs with $\mathrm{spf}(G) = 2$. On the other hand, we show that our main result is strictly more general than a previous generalization by Norine.