Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 1 h ago
PreprintCC BY-NC-SA 4.0arXiv

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

  • Enrique Junchaya
  • Cláudio L. Lucchesi
  • Alberto A. A. Miranda
Open at sourcePDFDOICite

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) ≤ 4g, 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) ≤ 2spf(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(K2n) = 2𝒪(n log n), an improvement on the previous upper bound of 4𝒪(n2) 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.

Related

  1. A Pfaffian Generalization of Hamilton-Jacobi Theory
    N N Fimin
    HALPreprintCC BY-NC-ND 4.0Full textGeneral mathematicsHAL
  2. Uniform generalization of Goodstein's theorem and Cichon's independence proof
    Gunnar Wilken
    arXivPreprintCC BY-NC-ND 4.0Full textLogic & foundationsarXiv
  3. A generalization of Gordon's Theorem to arbitrary winding number
    M. Fenucci
    arXivPreprintCC BY 4.0Full textDynamical systemsMathematical physicsarXiv
  4. A Generalization of Sárközy's theorem in function fields
    Pierre-Yves Bienvenu, Thái Hoàng Lê, Gauree Wathodkar
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
    Andrew D. Lin
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{junchaya2026symbolic,
  title = {{The symbolic pfaffian method I: A generalization of the Gallucio-Loebl-Tesler Theorem}},
  author = {Enrique Junchaya and Cláudio L. Lucchesi and Alberto A. A. Miranda},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.00468},
  eprint = {2611.00468},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.00468},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - The symbolic pfaffian method I: A generalization of the Gallucio-Loebl-Tesler Theorem
AU  - Enrique Junchaya
AU  - Cláudio L. Lucchesi
AU  - Alberto A. A. Miranda
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.00468
UR  - https://arxiv.org/abs/2611.00468
AB  - 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) ≤ 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) ≤ 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^𝒪(n log n), an improvement on the previous upper bound of 4^𝒪(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.
ER  -