Nima Anari (Theory Seminar)

Abstract: I will discuss an analytic property of multivariate polynomials, complete log-concavity, and its applications to problems in combinatorics and algorithmic tasks such as sampling, counting, and inference on discrete distributions. This property defines a large class of discrete distributions that should be thought of as the discrete analog of the well-studied continuous log-concave distributions. Examples of distributions satisfying this property include uniform distributions over bases or independent sets of matroids, determinantal point processes and fractional powers of them, and the random cluster model and Potts model for some regimes of parameters.

I will discuss a recipe for verifying this property and then give an application in which we resolve a combinatorial conjecture of Mason on the ultra-log-concavity of the number of independent sets of varying sizes in matroids. Then I will discuss connections to random sampling and the resolution of Mihail-Vazirani conjecture on the expansion of bases exchange graph.

Based on joint work with Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.