Counting matchings in irregular bipartite graphs and random lifts

DOI10.1137/1.9781611974782.146MaRDI QIDQ4575894zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(13)

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

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)