Exponential Lower Bounds for the Pfaffian Number of Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911701477097472 |
|---|---|
| author | Pant, Priyanshu Singh, Ranveer |
| author_facet | Pant, Priyanshu Singh, Ranveer |
| contents | Galluccio--Loebl and Tesler showed that the perfect-matching polynomial of a graph embedded in an orientable surface of genus $g$ can be written as a linear combination of at most $4^g$ Pfaffians. We show that, in general, exponentially many Pfaffians are necessary. More precisely, among all graphs of orientable genus at most $g$, the maximum possible Pfaffian number is at least $(8/3)^g$. This lower bound holds even for connected matching-covered graphs. We also obtain exponential lower bounds for the Pfaffian number of complete bipartite graphs, and hence for even complete graphs, improving asymptotically on a recent linear lower bound of Junchaya, Lucchesi, and Miranda. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_21077 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exponential Lower Bounds for the Pfaffian Number of Graphs Pant, Priyanshu Singh, Ranveer Combinatorics Discrete Mathematics 05C70, 05C10, 15A15 Galluccio--Loebl and Tesler showed that the perfect-matching polynomial of a graph embedded in an orientable surface of genus $g$ can be written as a linear combination of at most $4^g$ Pfaffians. We show that, in general, exponentially many Pfaffians are necessary. More precisely, among all graphs of orientable genus at most $g$, the maximum possible Pfaffian number is at least $(8/3)^g$. This lower bound holds even for connected matching-covered graphs. We also obtain exponential lower bounds for the Pfaffian number of complete bipartite graphs, and hence for even complete graphs, improving asymptotically on a recent linear lower bound of Junchaya, Lucchesi, and Miranda. |
| title | Exponential Lower Bounds for the Pfaffian Number of Graphs |
| topic | Combinatorics Discrete Mathematics 05C70, 05C10, 15A15 |
| url | https://arxiv.org/abs/2605.21077 |