Generalized Friedland-Tverberg inequality: applications and extensions

2006/03/16 by Shmuel Friedland, Friedland, Shmuel, Leonid Gurvits +1
Mathematics · #05A15 #05A16 #05C70 #05C80 #82B20 #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.math/0603410

openalex publication_date 2006/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We derive here the Friedland-Tverberg inequality for positive hyperbolic polynomials. This inequality is applied to give lower bounds for the number of matchings in r-regular bipartite graphs. It is shown that some of these bounds are asymptotically sharp. We improve the known lower bound for the three dimensional monomer-dimer entropy. We present Ryser-like formulas for computations of matchings in bipartite and general graphs. Additional algorithmic applications are given.

Citations

• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Concentration of permanent estimators for certain large matrices
• A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
• An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

Related

• Results and open problems in matchings in regular graphs
• Validations of the Asymptotic Matching Conjectures
• Asymptotics of the Upper Matching Conjecture
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's\n theorems
• Counting matchings in irregular bipartite graphs and random lifts