pith. sign in

arxiv: 2605.21077 · v1 · pith:HH6UEIQPnew · submitted 2026-05-20 · 🧮 math.CO · cs.DM

Exponential Lower Bounds for the Pfaffian Number of Graphs

Priyanshu Pant , Ranveer Singh This is my paper

Pith reviewed 2026-05-21 03:33 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords Pfaffian numberorientable genusperfect-matching polynomialmatching-covered graphscomplete bipartite graphs
0
0 comments X

The pith

The maximum Pfaffian number among graphs of orientable genus at most g is at least (8/3)^g.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Earlier work showed that the perfect-matching polynomial of any graph embedded on an orientable surface of genus g can be expressed as a linear combination of at most 4^g Pfaffians. This paper proves that exponentially many Pfaffians are sometimes required. It constructs families of graphs, including connected matching-covered ones, that attain a lower bound of (8/3)^g. The same exponential growth holds for the Pfaffian numbers of complete bipartite graphs and even complete graphs, improving on a prior linear lower bound.

Core claim

Among all graphs of orientable genus at most g the largest possible Pfaffian number is at least (8/3)^g; the bound continues to hold when the graphs are restricted to be connected and matching-covered. Exponential lower bounds are also obtained for the Pfaffian numbers of complete bipartite graphs and hence for even complete graphs.

What carries the argument

The Pfaffian number of a graph, defined as the smallest number of Pfaffians whose linear combination equals the perfect-matching polynomial.

If this is right

  • The known 4^g upper bound on the number of Pfaffians needed for genus-g graphs is not asymptotically tight.
  • Complete bipartite graphs require an exponential number of Pfaffians rather than a linear number.
  • Even complete graphs inherit exponential lower bounds on their Pfaffian numbers.
  • The exponential separation applies inside the subclass of connected matching-covered graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Algorithms that compute perfect-matchings counts via Pfaffian expansions on surfaces must in the worst case use time exponential in genus.
  • The construction technique may extend to other surface invariants that count signed perfect matchings.
  • Determining whether the base 8/3 can be replaced by a larger constant remains open and would tighten the gap to the 4^g upper bound.

Load-bearing premise

There exist families of graphs of genus exactly g whose perfect-matching polynomials cannot be written as linear combinations of fewer than (8/3)^g Pfaffians.

What would settle it

A single connected matching-covered graph of genus g whose perfect-matching polynomial equals a linear combination of fewer than (8/3)^g Pfaffians would falsify the stated lower bound.

Figures

Figures reproduced from arXiv: 2605.21077 by Priyanshu Pant, Ranveer Singh.

Figure 1
Figure 1. Figure 1: The graph G3. The blue edges are the added edges between consecutive copies of K3,3. We claim that Gg is matching-covered. Every edge inside a copy Ci lies in a perfect matching of Ci , and choosing arbitrary perfect matchings in all other blocks gives a perfect matching of Gg containing that edge. Now consider an added edge between Ci and Ci+1. Use both added edges aiβi+1, and bi+1αi . In Ci , the vertice… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript proves that the Pfaffian number of a graph of orientable genus at most g is at least (8/3)^g in the worst case. The lower bound is obtained by an explicit recursive construction of (connected, matching-covered) graphs whose perfect-matching polynomials are linearly independent over the reals when viewed as sign vectors; the genus of the constructed graphs is computed directly and matches the claimed bound. The same technique yields exponential lower bounds for complete bipartite graphs K_{n,n} (and hence for even complete graphs), improving the recent linear lower bound of Junchaya-Lucchesi-Miranda.

Significance. The result shows that the 4^g upper bound of Galluccio-Loebl and Tesler is not tight and that exponentially many Pfaffians are necessary for some surface graphs. The extension to matching-covered graphs and the explicit algebraic independence argument are technically substantive; the improvement for complete bipartite graphs is a clear asymptotic advance. If the constructions and independence proof hold, the paper supplies a concrete, falsifiable exponential separation that is likely to influence work on Pfaffian orientations and the complexity of the matching polynomial on surfaces.

major comments (1)
  1. [§3, Theorem 3.1] §3, Theorem 3.1 and the recursion in Definition 3.2: the linear-independence argument relies on the sign vectors of the constructed graphs being distinct under every possible signing; it is not immediately clear from the text whether the base-case vectors for g=0 remain independent after the genus-g embedding is imposed, or whether an additional relation could appear for large g. A short matrix-rank calculation or explicit small-g verification would strengthen the claim.
minor comments (2)
  1. [§2 and §4] The notation for the perfect-matching polynomial and the Pfaffian number is introduced in §2 but used interchangeably in §4; a single consistent symbol would improve readability.
  2. [Figure 1] Figure 1 (the base graph for the recursion) lacks edge labels; adding them would make the sign-vector computation easier to follow.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript and the constructive comment on the independence argument. We address the point below and will revise the text accordingly.

read point-by-point responses

  1. Referee: [§3, Theorem 3.1] §3, Theorem 3.1 and the recursion in Definition 3.2: the linear-independence argument relies on the sign vectors of the constructed graphs being distinct under every possible signing; it is not immediately clear from the text whether the base-case vectors for g=0 remain independent after the genus-g embedding is imposed, or whether an additional relation could appear for large g. A short matrix-rank calculation or explicit small-g verification would strengthen the claim.

    Authors: We thank the referee for this observation. The proof of Theorem 3.1 establishes linear independence of the sign vectors inductively on the genus parameter g. For the base case g=0 the construction yields a matching-covered graph (essentially a single edge) whose perfect-matching polynomial produces a sign vector that is a standard basis vector and hence linearly independent. The recursion in Definition 3.2 combines two copies of a genus-(g-1) graph by adding a new edge and a handle whose effect on the set of perfect matchings produces new sign vectors that extend the previous independent collection. This extension is realized by a block-triangular arrangement of the sign matrix whose determinant is nonzero whenever the previous matrix has full rank; consequently no linear dependence is introduced at any finite g. Because the surface embedding and the Pfaffian sign patterns are constructed simultaneously and explicitly, the genus bound is realized without imposing extra algebraic relations on the vectors. We agree that an explicit rank verification for small g would improve clarity. In the revised version we will insert a short paragraph immediately after the proof of Theorem 3.1 that records the 2-by-2 and 4-by-4 sign matrices for g=1 and g=2 together with their determinants, confirming that full rank is preserved. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The lower bound is obtained by explicit recursive constructions of families of graphs (including connected matching-covered ones) of genus exactly g, together with a direct algebraic argument establishing linear independence over the reals of the associated sign vectors. These steps rely on concrete graph operations and vector-space dimension counting rather than any fitted parameter, self-definition, or load-bearing self-citation that reduces the claim to its own inputs. The upper-bound reference to Galluccio-Loebl-Tesler is external and does not participate in the lower-bound derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions of Pfaffians, perfect-matching polynomials, and orientable genus from prior literature; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)
  • standard math Standard axioms and definitions of graph theory, linear algebra over fields, and the Pfaffian orientation for perfect matchings.
    The paper builds directly on the Galluccio-Loebl-Tesler framework and the definition of Pfaffian number.

pith-pipeline@v0.9.0 · 5651 in / 1280 out tokens · 37948 ms · 2026-05-21T03:33:13.275115+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · 1 internal anchor

  1. [1]

    Joseph Battle, Frank Harary, Yukihiro Kodama, and J. W. T. Youngs. Additivity of the genus of a graph.Bulletin of the American Mathematical Society, 68:565–568, 1962. doi:10.1090/S0002-9904-1962-10847-7

    work page doi:10.1090/s0002-9904-1962-10847-7 1962

  2. [2]

    A. Cayley. Sur les d´ eterminants gauches. (suite du m´ emoire t. xxxii. p. 119).Journal f¨ ur die reine und angewandte Mathematik, 38:93–96, 1849.doi:10.1515/crll.1849.38.93

    work page doi:10.1515/crll.1849.38.93

  3. [3]

    On the theory of pfaffian orientations

    Anna Galluccio and Martin Loebl. On the theory of pfaffian orientations. I. perfect matchings and permanents.Electronic Journal of Combinatorics, 6(1):R6, 1999.doi: 10.37236/1438

    work page doi:10.37236/1438 1999

  4. [4]

    John H. Halton. A combinatorial proof of Cayley’s theorem on Pfaffians.Journal of Combinatorial Theory, 1(2):224–232, 1966.doi:10.1016/S0021-9800(66)80029-7

    work page doi:10.1016/s0021-9800(66)80029-7 1966

  5. [5]

    Dickerson

    Enrique Junchaya, Alberto Alexandre Assis Miranda, and Cl´ audio L. Lucchesi. Lower bounds for the pfaffian number of graphs, 2026.arXiv:2603.00334,doi:10.48550/arXiv. 2603.00334

    work page internal anchor Pith review doi:10.48550/arxiv 2026

  6. [6]

    Kasteleyn

    Pieter W. Kasteleyn. The statistics of dimers on a lattice. I. the number of dimer ar- rangements on a quadratic lattice.Physica, 27(12):1209–1225, 1961.doi:10.1016/ 0031-8914(61)90063-5. 12

    work page 1961

  7. [7]

    Kasteleyn

    Pieter W. Kasteleyn. Graph theory and crystal physics. In Frank Harary, editor,Graph Theory and Theoretical Physics, pages 43–110. Academic Press, London, 1967

    work page 1967

  8. [8]

    C. H. C. Little. A characterization of convertible (0,1)-matrices.Journal of Combinatorial Theory, Series B, 18(3):187–208, 1975.doi:10.1016/0095-8956(75)90048-9

    work page doi:10.1016/0095-8956(75)90048-9 1975

  9. [9]

    Plummer.Matching Theory, volume 29 ofAnnals of Discrete Mathematics

    L´ aszl´ o Lov´ asz and Michael D. Plummer.Matching Theory, volume 29 ofAnnals of Discrete Mathematics. North-Holland, Amsterdam, 1986

    work page 1986

  10. [10]

    Lucchesi and U

    Cl´ audio L. Lucchesi and U. S. R. Murty.Perfect Matchings: A Theory of Matching Covered Graphs, volume 31 ofAlgorithms and Computation in Mathematics. Springer, Cham, 2024. doi:10.1007/978-3-031-47504-7

    work page doi:10.1007/978-3-031-47504-7 2024

  11. [11]

    P´ olya’s permanent problem.The Electronic Journal of Combinatorics, 11(1):R79, 2004.doi:10.37236/1832

    William McCuaig. P´ olya’s permanent problem.The Electronic Journal of Combinatorics, 11(1):R79, 2004.doi:10.37236/1832

    work page doi:10.37236/1832 2004

  12. [12]

    Matching signatures and pfaffian graphs.Discrete Mathematics, 311(4):289–294, 2011.doi:10.1016/j.disc

    Alberto Alexandre Assis Miranda and Cl´ audio Leonardo Lucchesi. Matching signatures and pfaffian graphs.Discrete Mathematics, 311(4):289–294, 2011.doi:10.1016/j.disc. 2010.10.014

    work page doi:10.1016/j.disc 2011

  13. [13]

    Sergey Norin, C. H. C. Little, and Kee L. Teo. A new proof of a characterisation of pfaffian bipartite graphs.Journal of Combinatorial Theory, Series B, 91(1):123–126, 2004. doi:10.1016/j.jctb.2003.10.004

    work page doi:10.1016/j.jctb.2003.10.004 2004

  14. [14]

    Drawing 4-pfaffian graphs on the torus.Combinatorica, 29(1):109–119, 2009.doi:10.1007/s00493-009-2354-0

    Serguei Norine. Drawing 4-pfaffian graphs on the torus.Combinatorica, 29(1):109–119, 2009.doi:10.1007/s00493-009-2354-0

    work page doi:10.1007/s00493-009-2354-0 2009

  15. [15]

    Aufgabe 424.Archiv der Mathematik und Physik, 20:271, 1913

    George P´ olya. Aufgabe 424.Archiv der Mathematik und Physik, 20:271, 1913

    work page 1913

  16. [16]

    Seymour, and Robin Thomas

    Neil Robertson, Paul D. Seymour, and Robin Thomas. Permanents, Pfaffian orientations, and even directed circuits.Annals of Mathematics, 150(3):929–975, 1999.doi:10.2307/ 121059

    work page 1999

  17. [17]

    Matchings in graphs on non-orientable surfaces.Journal of Combinatorial Theory, Series B, 78(2):198–231, 2000.doi:10.1006/jctb.1999.1941

    Glenn Tesler. Matchings in graphs on non-orientable surfaces.Journal of Combinatorial Theory, Series B, 78(2):198–231, 2000.doi:10.1006/jctb.1999.1941

    work page doi:10.1006/jctb.1999.1941 2000

  18. [18]

    Leslie G. Valiant. The complexity of computing the permanent.Theoretical Computer Science, 8(2):189–201, 1979.doi:10.1016/0304-3975(79)90044-6. 13

    work page doi:10.1016/0304-3975(79)90044-6 1979