CS Paper Radar

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

Enrique Junchaya, Cláudio L. Lucchesi, Alberto A. A. Miranda

cs.DM math.CO ·submitted 2026-10-30 23:47 UTC · v1
theory

Abstract

The pfaffian number of a graph $G$, denoted by $\mathrm{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 $\mathrm{pf}(G) \leq 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 $\mathrm{spf}(G)$. Namely, we prove that $\mathrm{pf}(G) \leq 2^{\mathrm{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 $\mathrm{pf}(K_{2n}) = 2^{\mathcal{O}(n \log n)}$, an improvement on the previous upper bound of $4^{\mathcal{O}(n^2)}$ based on the genus. We also consider lower bounds for $\mathrm{pf}(G)$ related to $\mathrm{spf}(G)$. In particular, we show that the graphs with $\mathrm{pf}(G) = 4$ are the graphs with $\mathrm{spf}(G) = 2$. On the other hand, we show that our main result is strictly more general than a previous generalization by Norine.

Comment
20 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

An Odd Pfaffian Number

cs.DM math.CO ·2026-09-19 ·Priyanshu Pant, Ranveer Singh
similarity 0.67
Abstract

The Pfaffian number of a graph is the minimum number of Pfaffians needed to obtain its perfect-matching polynomial by linear combination. In 2009, Norine conjectured that every Pfaffian number is a power of four. Miranda and Lucchesi disproved this conjecture in 2011 by constructing a graph of Pfaffian number six, and conjectured instead that every nontrivial Pfaffian number is even. We disprove their conjecture by proving that the Pfaffian number of $K_{3,3}\sqcup K_{3,3}$ is 13. We also construct a connected cubic bipartite matching-covered graph with Pfaffian number 13.

0.18

Coloring graphs with no long induced path

cs.DM math.CO ·2026-09-08 ·Sang-il Oum
similarity 0.61
Abstract · 8 pages; the bound is improved; Added references and clarified attribution of the proof methods

Let $P_t$ denote the induced path on $t$ vertices. Let $ω(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gyárfás (1987) proved that every $P_t$-free graph $G$ satisfies $χ(G)\le(t-1)^{ω(G)-1}$, and Gravier, Hoàng, and Maffray (2003) improved this to $χ(G)\le (t-2)^{ω(G)-1}$ for $t\ge4$. We lower the base of the exponential by one: for every $t\ge5$, every $P_t$-free graph $G$ satisfies \[ χ(G)\le 3\,(t-3)^{ω(G)+4}. \] The proof combines two refinements of the Gyárfás path argument and was developed with the assistance of Claude Fable 5.1 of Anthropic and GPT Pro of OpenAI.

0.46

Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials

cs.DM math.CO ·2026-09-14 ·Fangfang Lin, Hong Zhou
theory similarity 0.60
Abstract · 25 pages, slightly improved bound for graphs of girth at least 5, include some recent progress

Bilu and Linial conjectured that every finite $d$-regular graph with $d \geq 2$ admits an edge signing $σ$ whose signed adjacency matrix $A_σ$ has spectral radius at most $2\sqrt{d-1}$. We prove that every signing meeting the mixed-root condition $r_{A_σ}\leq\sqrt{2(d-1)}$ satisfies \[ ρ(A_σ) < \frac{3+\sqrt5}{2}\sqrt{d-1}, \] where $r_{A_σ}$ is the largest root of the mixed determinantal polynomial $χ[A_σ,-A_σ]$. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient $2\sqrt2$ in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of $χ[A_σ,-A_σ]$. The second moment gives a simple matrix inequality $A_σ^2 + dI \preceq 4r_{A_σ}^2I$, which yields a preliminary coefficient $\sqrt{7}$. Estimates for the fourth moment use information about short walks to obtain the coefficient $(3+\sqrt{5})/2$. For triangle-free graphs, the coefficient improves to $\sqrt6$, and for graphs with girth at least five, it improves to $\sqrt{35/6}$. As a result of independent interest, we extend the construction to $χ[A_1,\ldots,A_k]$ for Hermitian matrices $A_1,\ldots,A_k$ with zero diagonal, and compute the first two moments explicitly. Finally, an explicit signing of $K_8$ shows that the mixed-root condition alone cannot guarantee a coefficient below $(4+\sqrt5)/\sqrt6$.

0.55

Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers

cs.DM math.CO ·2026-10-10 ·Yusuke Watanabe
theorycode/data similarity 0.60
Abstract · 39 pages. Main Theorems A-C formalized in Lean 4; code: https://github.com/ywatanabex/coefficientwise-rigidity-lean

Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde G$ with those of the trivial cover, consisting of $M$ disjoint copies of $G$, after prescribing how many vertices are selected above each vertex of $G$. A conjecture from 2011, motivated by the Bethe approximation, asserts that the trivial cover maximizes every such count. We prove this for every feasible occupation profile whose active graph has treewidth at most two or is chordal bipartite. Equality holds exactly when the restricted cover is flat, meaning that fibre relabelings make it trivial. For $M\ge2$ and positive feasible occupations, a nonflat cover of a connected bipartite graph of treewidth at most two has a deficit of at least twice the coefficient of $p_G^{M-2}$ with every occupation reduced by one. A holonomy-dependent bound improves the factor to three for odd-order holonomy; both uniform constants are sharp. Comparison and rigidity survive finite compositions along an edge or a vertex, and quantitative bounds from one piece propagate to the whole graph, giving results beyond the two original classes. On any bipartite base, the first nonzero homogeneous defect is determined by the shortest cycles with nontrivial holonomy. At singleton occupations, our counts are numbers of DP-colorings of full covers. The dual DP color function on these classes and their finite seam compositions equals the chromatic polynomial, with equality attained precisely by canonical labelings. Dong's chromatic-polynomial inequality then yields the Dual-DP Shameful inequality on the same graph class. The main theorems have been formalized in Lean 4.

0.28

A simplified proof of the FPRAS for counting perfect matchings

cs.DS math.CO ·2026-10-19 ·Chenghua Liu, Boning Meng
similarity 0.59
Abstract

We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.

0.26

Logarithmic basis number of graphs and regular matroids

cs.DM math.CO ·2026-09-02 ·Kolja Knauer
theory similarity 0.59
Abstract · 13 pages

The basis number $bn(G)$ of a graph $G$ is the minimum edge-congestion of a basis of its cycle space. We prove that every finite $n$-vertex multigraph satisfies $bn(G)=O(\log n)$, resolving, for simple graphs, a question of Bazargani, Biedl, Bose, Maheshwari and Miraftab, subsequently stated as a conjecture by Miraftab, Morin and Yuditsky. The argument also yields the cycle-rank refinement $bn(G)=O(\log β(G))$, where $β(G)$ is the dimension of the cycle space, and a reduction of Lehner and Miraftab, based on a theorem of Richter and Shank, then gives $bn(G)=O(\log g)$ for graphs of Euler genus $g$. For regular matroids we prove the ground-set bound $bn(M)=O(\log m)$, where $m=|E(M)|$, and logarithmic bounds in both the rank $r(M)$ and the cycle-space dimension $d$. All these orders are best possible.

0.51

Pfaffian Recognition is in $\mathsf{coRP}$

cs.CC cs.DM ·2026-10-21 ·Priyanshu Pant, Ranveer Singh
similarity 0.58
Abstract · Major revision with a new structural characterization of Pfaffian orientations and its consequences

An orientation of a graph is called Pfaffian if all perfect matchings occur with the same sign in its Pfaffian expansion. A graph is Pfaffian if it admits such an orientation. Given a Pfaffian orientation, the number of perfect matchings can be computed in polynomial time. In 1963, Kasteleyn showed that every planar graph is Pfaffian. In 1989, Vazirani and Yannakakis showed that deciding whether a graph is Pfaffian is polynomial time equivalent to testing whether a given orientation is Pfaffian. For bipartite graphs, polynomial time recognition algorithms were obtained by Robertson, Seymour, and Thomas in 1999, and independently by McCuaig in 2004. Whether a deterministic polynomial time algorithm exists for general graphs remains open. In this paper, we first construct a polynomial that is identically zero if and only if a given orientation is Pfaffian, and show that this polynomial can be evaluated in polynomial time. Combined with the reduction of Vazirani and Yannakakis, this gives a randomized polynomial time algorithm for deciding whether a general graph is Pfaffian, placing the problem in $\mathsf{coRP}$. We also prove that an orientation of a matching covered graph is non-Pfaffian if and only if reversing the edges of some cut makes it strongly connected. Although deciding whether such a cut exists is NP-complete for general digraphs, our characterization yields a randomized polynomial time algorithm for matching covered graphs and deterministic polynomial time algorithms for bipartite and planar matching covered graphs.

0.20

A 3-regular counterexample to the Bilu--Linial signing conjecture

cs.DM math.CO ·2026-09-14 ·Zhiqiang Xu
similarity 0.58
Abstract · 19 pages, 5 figures. The presentation has been improved

We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside $[-2\sqrt2,2\sqrt2]$. This disproves the Bilu--Linial signing conjecture for general regular graphs. The graph $F$ is not Ramanujan, and the conjecture restricted to Ramanujan base graphs remains open.

0.62