Lower Bounds for the Pfaffian Number of Graphs
math.CO, cs.DM
Submitted: 2026-02-27
Updated: 2026-02-27
Comments: 14 pages, 3 figures. Submitted
Journal ref: LIPIcs --- Leibniz Int. Proc. Inform. 376 (2026), 28:1-28:15
DOI: 10.4230/LIPIcs.WG.2026.28
License: http://creativecommons.org/licenses/by/4.0/
The gist: The number of perfect matchings of a k-pfaffian graph can be counted by computing a linear combination of the pfaffians of k matrices.
Terminology
Abstract
The number of perfect matchings of a k-pfaffian graph can be counted by computing a linear combination of the pfaffians of k matrices. The pfaffian number of a graph G is the smallest integer k such that G is k-pfaffian. We present the first known lower bounds for the pfaffian number of graphs. As an intermediate step, we prove an upper bound for the rank of two matrices related to their Khatri-Rao product, a result of independent relevance. One of the consequences of these results is the existence of graphs whose pfaffian numbers are arbitrarily large.
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