Graph theory paper finds unexpected odd number in perfect matchings
An Odd Pfaffian Number
Discrete Mathematics
Summary
This paper studies a special number called the Pfaffian number, which relates to counting perfect matchings in graphs, a kind of network. Earlier mathematicians guessed all these numbers would be powers of four or at least even, but the authors found examples where this number is 13, an odd number. This breaks previous assumptions and shows the topic is more complex than thought. They also built a connected graph with this odd Pfaffian number.
What this means in practice
- •For graph algorithm designers: Avoid assuming Pfaffian numbers must be powers of four or even when optimizing algorithms that rely on perfect matching polynomials.
- •For network modelers: Use new examples of graphs with odd Pfaffian numbers to better understand structural properties impacting network robustness and connectivity.
A theory result. No direct application yet.
Authors
Priyanshu Pant, Ranveer Singh
Abstract
The Pfaffian number of a graph is the minimum number of Pfaffians needed to obtain its perfect-matching polynomial by linear combination. In 2009, Norine conjectured that every Pfaffian number is a power of four. Miranda and Lucchesi disproved this conjecture in 2011 by constructing a graph of Pfaffian number six, and conjectured instead that every nontrivial Pfaffian number is even. We disprove their conjecture by proving that the Pfaffian number of $K_{3,3}\sqcup K_{3,3}$ is 13. We also construct a connected cubic bipartite matching-covered graph with Pfaffian number 13.