Counting matchings in irregular bipartite graphs and random lifts

DOI10.1137/1.9781611974782.146zbMATH Open1410.05168arXiv1507.04739OpenAlexW2144865572MaRDI QIDQ4575894FDOQ4575894

Authors: Marc Lelarge 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We give a sharp lower bound on the number of matchings of a given size in a bipartite graph. When specialized to regular bipartite graphs, our results imply Friedland's Lower Matching Conjecture and Schrijver's theorem proven by Gurvits and Csikvari. Indeed, our work extends the recent work of Csikvari done for regular and bi-regular bipartite graphs. Moreover, our lower bounds are order optimal as they are attained for a sequence of $2$-lifts of the original graph as well as for random $n$-lifts of the original graph when $n$ tends to infinity. We then extend our results to permanents and subpermanents sums. For permanents, we are able to recover the lower bound of Schrijver recently proved by Gurvits using stable polynomials. Our proof is algorithmic and borrows ideas from the theory of local weak convergence of graphs, statistical physics and covers of graphs. We provide new lower bounds for subpermanents sums and obtain new results on the number of matching in random $n$-lifts with some implications for the matching measure and the spectral measure of random $n$-lifts as well as for the spectral measure of infinite trees.

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

Recommendations

• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Matchings in vertex-transitive bipartite graphs
• On the number of perfect matchings in random lifts
• Results and open problems in matchings in regular graphs
• On the number of matchings in regular graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (13)

• A short survey on stable polynomials, orientations and matchings
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Gauges, loops, and polynomials for partition functions of graphical models
• Matchings in Benjamini-Schramm convergent graph sequences
• Matchings in vertex-transitive bipartite graphs
• A generalization of permanent inequalities and applications in counting and optimization
• Counting irregular multigraphs
• On the number of perfect matchings in random lifts
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• Statistical Matching Theory
• Equitable partition for some Ramanujan graphs
• Tight bounds on the coefficients of partition functions via stability
• Matchings in random biregular bipartite graphs

This page was built for publication: Counting matchings in irregular bipartite graphs and random lifts

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