Counting Matchings via Capacity Preserving Operators

DOI10.1017/S0963548321000122arXiv1804.04351MaRDI QIDQ6300258FDOQ6300258

Publication date: 12 April 2018

Abstract: The notion of the capacity of a polynomial was introduced by Gurvits around 2005, originally to give drastically simplified proofs of the Van der Waerden lower bound for permanents of doubly stochastic matrices and Schrijver's inequality for perfect matchings of regular bipartite graphs. Since this seminal work, the notion of capacity has been utilized to bound various combinatorial quantities and to give polynomial-time algorithms to approximate such quantities (e.g., the number of bases of a matroid). These types of results are often proven by giving bounds on how much a particular differential operator can change the capacity of a given polynomial. In this paper, we unify the theory surrounding such capacity preserving operators by giving tight capacity preservation bounds for all nondegenerate real stability preservers. We then use this theory to give a new proof of a recent result of Csikv'ari, which settled Friedland's lower matching conjecture.

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Inequalities involving derivatives and differential and integral operators (26D10) Combinatorial inequalities (05A20) Real polynomials: location of zeros (26C10)

This page was built for publication: Counting Matchings via Capacity Preserving Operators

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