Generalized Friedland-Tverberg inequality: applications and extensions

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.

21 pages, 2 figures

References in corpus (3)

• Concentration of permanent estimators for certain large matrices
• Combinatorial and algorithmic aspects of hyperbolic polynomials
• A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs

Cited by in corpus (5)

• Validations of the Asymptotic Matching Conjectures
• A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
• Analogs of the van der Waerden and Tverberg conjectures for haffnians
• On the Number of Matchings in Regular Graphs
• FPRAS for computing a lower bound for weighted matching polynomial of graphs