Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems

DOI10.4171/JEMS/706zbMath1362.05065arXiv1406.0766OpenAlexW2963684960WikidataQ123264878 ScholiaQ123264878MaRDI QIDQ2628330

Péter Csikvári

Publication date: 1 June 2017

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.0766

zbMATH Keywords

matchingsmatching polynomialBenjamini-Schramm convergenceinfinite regular tree2-liftinfinite biregular tree

Mathematics Subject Classification ID

Graph polynomials (05C31) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (15)

Positivity of the virial coefficients in lattice dimer models and upper bounds on the number of matchings on graphs ⋮ Counting matchings via capacity-preserving operators ⋮ Matchings in regular graphs: minimizing the partition function ⋮ On the average size of independent sets in triangle-free graphs ⋮ Upper bound for the number of spanning forests of regular graphs ⋮ Statistical Matching Theory ⋮ Matchings in vertex-transitive bipartite graphs ⋮ A generalization of permanent inequalities and applications in counting and optimization ⋮ A positivity property of the dimer entropy of graphs ⋮ Tight bounds on the coefficients of partition functions via stability ⋮ On the number of forests and connected spanning subgraphs ⋮ Atoms of the matching measure ⋮ Covers, orientations and factors ⋮ A Tight Analysis of Bethe Approximation for Permanent ⋮ A short survey on stable polynomials, orientations and matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The matching energy of a graph
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• Benjamini-Schramm continuity of root moments of graph polynomials
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
• On the number of matchings in regular graphs
• The number of matchings in random regular graphs and bipartite graphs
• Probabilistic bounds on the coefficients of polynomials with only real zeros
• Counting 1-factors in regular bipartite graphs
• Theory of monomer-dimer systems
• Matchings in Benjamini–Schramm convergent graph sequences
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• On Leonid Gurvits’s Proof for Permanents
• A Remark on Stirling's Formula
• On the Distribution of the Number of Successes in Independent Trials
• Borel oracles. An analytical approach to constant-time algorithms
• Counting matchings in irregular bipartite graphs and random lifts
• On the Number of Perfect Matchings in Random Lifts
• On the Distribution of the Number of Successes in Independent Trials

This page was built for publication: Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems