CS Paper Radar

Optimal girth-dependent bounds for the Bethe approximation of the permanent

Dingding Dong, Vishesh Jain

cs.DS math.CO ·submitted 2026-09-02 02:45 UTC · v1
theoryhot direction

Abstract

For an $n\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{n/2}\operatorname{Bethe}(A).\] The lower bound, due to Gurvits, is attained on forests. The upper bound, due to Anari and Rezaei, is attained by the adjacency matrix of a disjoint union of $4$-cycles. Confirming a conjecture of Anari, we provide an optimal girth-dependent refinement of the above comparison. More precisely, we show that if the bipartite support graph of $A$ has girth at least an even integer $g \geq 4$, then \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{2n/g}\operatorname{Bethe}(A).\] The upper bound is attained by the adjacency matrix of a disjoint union of $g$-cycles.

Comment
21 pages; comments welcome!

Closest papers

Nearest neighbours by meaning across the whole index.

Structural Corrections to the Bethe Approximation of the Permanent

cs.DS math.CO ·2026-08-31 ·Ijay Narang, Will Perkins
hot direction similarity 0.76
Abstract

We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight analysis of Anari and Rezaei gives a universal comparison between the permanent and the Bethe permanent within a factor $(\sqrt 2)^n$. The simple example of the unweighted $4$-cycle $C_4$ (or a union of disjoint $C_4$'s) shows that this bound is tight. We show that such $4$-cycle obstructions can be identified and exploited algorithmically. Given a Bethe optimizer, our algorithm identifies nearly isolated weighted $2\times2$ blocks and peels off a vertex-disjoint family of them. If the total weighted correction is large, we can improve the Bethe approximation; if it is small, we show that the Bethe permanent is within a factor of $(\sqrt2 - \varepsilon)^n$ of the truth. Combining these facts, we obtain a deterministic polynomial time $(\sqrt2-\varepsilon)^n$-approximation algorithm for the permanent of an arbitrary nonnegative $n\times n$ matrix, where $\varepsilon>0$ is some absolute constant.

0.45

Beyond the Bethe Approximation of the Permanent

cs.DS math.CO ·2026-08-28 ·Nima Anari
theorycode/data similarity 0.69
Abstract · 34 pages. Accompanying Lean 4 formalization: https://github.com/nimaanari/formalization-beyond-bethe. Palomar Registry entry: https://paloma…

The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of $(\sqrt{2})^n$. We improve the base of this exponential factor: for some absolute constant $c<\sqrt{2}$, there is a deterministic polynomial-time $c^n$-approximation for the permanent of every nonnegative matrix. This shows that the canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent. The proof augments the Bethe lower bound with a new certificate tailored to matrices on which that lower bound loses nearly the full factor. The author supplied the high-level plan of attack, and the proof was developed in an interaction with ChatGPT 5.6 Sol Pro. The author subsequently verified the results. Codex assisted with proof checking, manuscript assembly, and typesetting.

0.67

Asymptotically Optimal Bounds for Counting Near-Minimum Circuits in Regular Matroids

cs.DM math.CO ·2026-11-11 ·Robert P. Streit
theory similarity 0.64
Abstract · 28 pages

For a regular matroid on $m$ elements with positive weights and weighted girth $g_w$, we prove that the number of circuits of weight at most $αg_w$ is bounded by $(Km)^{2α}$, for every real $α\ge1$ and an absolute constant $K$. This improves the previous $m^{O(α^2)}$ bound of Gurjar and Vishnoi and matches classic graph cut and cycle counting bounds of Karger and Subramanian. We also show this is asymptotically optimal for all real $α\geq 1$ under the Erdős girth conjecture, while unconditional optimality holds for half-integer $α$ by prior results. As consequences, we resolve a recent conjecture by Khanna, Putterman, and Song implying the existence of a parallel basis search algorithm for regular matroids terminating in logarithmically many rounds of independence queries, and obtain improved bounds on the number of near-minimum weight codewords in regular codes and near-shortest vectors in totally unimodular lattices under $\ell_p$-norms.

0.23

Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers

cs.DM math.CO ·2026-10-10 ·Yusuke Watanabe
theorycode/data similarity 0.63
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

Integral saturation of adjacency-degree lattices

cs.DM math.CO ·2026-11-01 ·Zhipeng Lu
theory similarity 0.61
Abstract

Let $A$ be the adjacency matrix of $G\sim G(n,1/2)$, let $D=\operatorname{diag}(A\mathbf{1})$, and let $Λ_G=\mathbb{Z}\langle A,D\rangle\mathbf{1}$. We prove $\Pr[Λ_G\ne\mathbb{Z}^n]\le n^{-3/20+o(1)}$. Thus two dependent graph operators generate the entire vertex lattice from the constant vector, simultaneously over every prime field. Adjacency alone has a modulo-two rank obstruction for every simple graph of order greater than one, even though its rational word span is typically full. The proof first constructs words containing at most two adjacency operations whose integer span contains $Δ_G^3\mathbb{Z}^n$, where $Δ_G$ is the product of the pairwise differences between distinct degree values. This confines all possible arithmetic obstructions to a finite prime range on a single event. We then remove the remaining obstructions using conditional alternating forms, symmetric random-matrix code estimates, and uniform counts of degree-graded invariant subspaces. We connect the integer lattice to graph reconstruction through pointed moments. Saturation forces every pointed orthogonal AD intertwiner to be a vertex permutation. The short-word construction also shows that a fixed polynomial-size family of ordinary caterpillars, of diameter at most seven and order $O(\sqrt{n\log n})$, identifies almost every graph among all finite simple graphs. For nonsaturated full-rank lattices, we give an exact description of the moment fibre by admissible unimodular overlattices; at index two, the only possible ambiguity is a specified four-vertex Godsil--McKay switch.

0.28

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.60
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Logarithmic basis number of graphs and regular matroids

cs.DM math.CO ·2026-09-02 ·Kolja Knauer
theory similarity 0.60
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

Lower Bounds for Domination-Type Problems Parameterized by Rank-Width

cs.CC ·2026-08-19 ·Chenghua Liu, Boning Meng
theory similarity 0.60
Abstract

For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((σ,ρ)\)-problems and of Bergougnoux and Kanté (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for \emph{Weighted} Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no \(2^{o(w^2)}n^{O(1)}\)-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry \(k^2\) assignment bits through cuts of rank \(O(k)\). The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of \((σ,ρ)\)-set problems. This family includes cases in which \(σ\) is neither finite nor cofinite and contains the entire nontrivial cofinite--cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis (\(\#\mathrm{ETH}\)), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width \(w\) is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.

0.18