Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More

We introduce two new notions for polynomials associated with discrete set-valued probability distributions. These notions generalize well-studied properties like real-stability and log-concavity, but unlike them robustly degrade under a number of useful transformations applied to the polynomial/distribution. We show that these notions imply polynomial time approximate sampling and counting algorithms through rapid mixing of multi-site Glauber dynamics. We establish the new notions for polynomials/distributions related to matchings, Pfaffian point processes, and partition-constrained strongly Rayleigh measures with O(1) partitions. As the main application we show how to approximately count matchings of a desired size k, or sample from the monomer-dimer distribution, in arbitrary planar graphs (not necessarily bipartite) in polynomial time; this answers a question raised by Jerrum in 1987 who proved intractability of exact counting in the planar case.

 

Joint work with Yeganeh Alimohammadi, Kirankumar Shiragur, and Thuy-Duong Vuong.

Date

Speakers

Nima Anari

Affiliation

Stanford University