Lower Bounds for the Pfaffian Number of Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910035874938880 |
|---|---|
| author | Junchaya, Enrique Miranda, Alberto Alexandre Assis Lucchesi, Cláudio L. |
| author_facet | Junchaya, Enrique Miranda, Alberto Alexandre Assis Lucchesi, Cláudio L. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_00334 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for the Pfaffian Number of Graphs Junchaya, Enrique Miranda, Alberto Alexandre Assis Lucchesi, Cláudio L. Combinatorics Discrete Mathematics 05C85 (Primary), 05C70, 68R10 (Secondary) G.2.2 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. |
| title | Lower Bounds for the Pfaffian Number of Graphs |
| topic | Combinatorics Discrete Mathematics 05C85 (Primary), 05C70, 68R10 (Secondary) G.2.2 |
| url | https://arxiv.org/abs/2603.00334 |