Open Research Index

Lower Bounds for the Pfaffian Number of Graphs

Enrique Junchaya, Alberto Alexandre Assis Miranda, Cláudio L. Lucchesi

arXivarxiv/2603.00334Feb 27, 2026math.COscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2603.00334
curl -X POST /api/v1/records/arxiv/2603.00334/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.00334/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'