2011/06/14 by Leonid Gurvits, Gurvits, Leonid · 4 citations
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Information Theory (cs.IT) #Mathematical Inequalities and Applications #Mathematical Physics (math-ph) #Mathematics and Applications #Matrix Theory and Algorithms #cs.CC #cs.IT #math-ph #math.CO #math.IT #math.MP
paper · pdf · doi:10.48550/arxiv.1106.2844
30 pages, more typos are fixed, more remarks are added, importantly a concrete counter-example to [Lu,Mohr,Szekely] positive correlation conjecture is presented
openalex publication_date 2011/06/14 · arxiv created 2012/06/20 · arxiv updated 2012/06/21 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Let A ∈ Ωn be doubly-stochastic n × n matrix. Alexander Schrijver proved in 1998 the following remarkable inequality per(\widetildeA) ≥ ∏1 ≤ i,j ≤ n (1- A(i,j)); \widetildeA(i,j) =: A(i,j)(1-A(i,j)), 1 ≤ i,j ≤ n. We use the above Shrijver's inequality to prove the following lower bound: (per(A))/(F(A)) ≥ 1; F(A) =: ∏1 ≤ i,j ≤ n (1- A(i,j))1- A(i,j). We use this new lower bound to prove S.Friedland's Asymptotic Lower Matching Conjecture(LAMC) on monomer-dimer problem. We use some ideas of our proof of (LAMC) to disprove [Lu,Mohr,Szekely] positive correlation conjecture. We present explicit doubly-stochastic n × n matrices A with the ratio (per(A))/(F(A)) = √(2)n; conjecture that maxA ∈ Ωn(per(A))/(F(A)) ≈ (√(2))n and give some examples supporting the conjecture. If true, the conjecture (and other ones stated in the paper) would imply a deterministic poly-time algorithm to approximate the permanent of n × n nonnegative matrices within the relative factor (√(2))n. The best current such factor is en.