Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 5 min ago
PreprintCC BY 4.0arXiv

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

  • Dingding Dong
  • Vishesh Jain
Open at sourcePDFDOICite

Abstract

For an n× n nonnegative matrix A, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison Bethe(A) ≤ per(A) ≤ 2n/2Bethe(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 ≥ 4, then Bethe(A) ≤ per(A) ≤ 22n/gBethe(A). The upper bound is attained by the adjacency matrix of a disjoint union of g-cycles.

Related

  1. Bounds-Constrained Finite Element Approximation of Time-Dependent Partial Differential Equations
    Robert C. Kirby, John D. Stephens
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
  2. Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
    Yi-Chun Akchen, Sena Asli Bozkurt, Chen-An Lin
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Optimal CLT error bounds in the second order Wasserstein metric via Stein's method for weakly dependent sequences
    Yeor Hafouta, Juho Leppanen
    arXivPreprintarXiv licenceFull textDynamical systemsProbabilityarXiv
  4. A deterministic (1+ε)n approximation for the permanent of a nonnegative matrix
    Dingding Dong, Vishesh Jain
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Asymptotic Spectral Bounds under Odd-Girth Constraints
    Chen Wang
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{dong2026optimal,
  title = {{Optimal girth-dependent bounds for the Bethe approximation of the permanent}},
  author = {Dingding Dong and Vishesh Jain},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02017},
  eprint = {2609.02017},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02017},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Optimal girth-dependent bounds for the Bethe approximation of the permanent
AU  - Dingding Dong
AU  - Vishesh Jain
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.02017
UR  - https://arxiv.org/abs/2609.02017
AB  - For an n× n nonnegative matrix A, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison Bethe(A) ≤ per(A) ≤ 2^n/2Bethe(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 ≥ 4, then Bethe(A) ≤ per(A) ≤ 2^2n/gBethe(A). The upper bound is attained by the adjacency matrix of a disjoint union of g-cycles.
ER  -