Lower Bounds for Partial Matchings in Regular Bipartite Graphs and Applications to the Monomer–Dimer Entropy

DOI10.1017/S0963548307008747MaRDI QIDQ3545903zbMATH OpenOpenAlexFDO

Authors Leonid Gurvits, S. Friedland

Publication date 11 December 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548307008747

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the validations of the asymptotic matching conjectures
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• \(1/n\) expansion for the number of matchings on regular graphs and Monomer-Dimer entropy
• Matchings and independent sets of a fixed size in regular graphs
• Results and open problems in matchings in regular graphs

Cites work

• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• A lower bound for the permanent of a doubly stochastic matrix
• A lower bound on the maximum permanent in \(\Lambda_{n}^{k}\).
• A proof of a generalized van der Waerden conjecture on permanents
• Counting 1-factors in regular bipartite graphs
• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• On the Permanent of a Bistochastik Matrix.
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Theory of computation of multidimensional entropy with an application to the monomer-dimer problem
• Theory of monomer-dimer systems

Cited in

(9)

• A positivity property of the dimer entropy of graphs
• On the validations of the asymptotic matching conjectures
• Positivity of the virial coefficients in lattice dimer models and upper bounds on the number of matchings on graphs
• Sequential cavity method for computing free energy and surface pressure
• \(1/n\) expansion for the number of matchings on regular graphs and Monomer-Dimer entropy
• Statistical Matching Theory
• Nash social welfare, matrix permanent, and stable polynomials
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• Counting matchings via capacity-preserving operators

This page was built for publication: Lower Bounds for Partial Matchings in Regular Bipartite Graphs and Applications to the Monomer–Dimer Entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3545903)