Bounding the Bethe and the Degree-M Bethe Permanents

2015/03/07 by Roxana Smarandache, Smarandache, Roxana, Martin Haenggi +1
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Graph theory and applications #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #cs.CC #cs.IT #math-ph #math.CO #math.IT #math.MP

paper · pdf · doi:10.48550/arxiv.1503.02217

arxiv created 2015/03/07 · openalex publication_date 2015/03/07 · arxiv updated 2015/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

It was recently conjectured that the permanent of a P-lifting θ^\uparrowP of a matrix θ of degree M is less than or equal to the Mth power of the permanent perm(θ), i.e., perm(θ^\uparrowP)≤(perm(θ))^M and, consequently, that the degree-M Bethe permanent perm_M,B (θ) of a matrix θ is less than or equal to the permanent perm(θ) of θ, i.e., perm_{M, B} (θ)≤ perm(θ). In this paper, we prove these related conjectures and show in addition a few properties of the permanent of block matrices that are lifts of a matrix. As a corollary, we obtain an alternative proof of the inequality perm_B (θ)≤ perm(θ) on the Bethe permanent of the base matrix θ that uses only the combinatorial definition of the Bethe permanent.

Citations

• Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
• Approximating the Permanent with Belief Propagation

Related

• Degree-M Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-negative Matrix
• A Tight Analysis of Bethe Approximation for Permanent
• Pseudocodewords from Bethe Permanents
• Double-cover-based analysis of the Bethe permanent of non-negative matrices
• A stability result using the matrix norm to bound the permanent