Completely log-concave polynomials and matroids

ACO Colloquium
Friday, April 12, 2019 - 3:05pm for 1 hour (actually 50 minutes)
Skiles 005
Cynthia Vinzant – North Carolina State University, Raleigh, NC
Prasad Tetali

Stability is a multivariate generalization for real-rootedness in univariate polynomials. Within the past ten years, the theory of stable polynomials has contributed to breakthroughs in combinatorics, convex optimization, and operator theory. I will introduce a generalization of stability, called complete log-concavity, that satisfies many of the same desirable properties. These polynomials were inspired by work of Adiprasito, Huh, and Katz on combinatorial Hodge theory, but can be defined and understood in elementary terms. The structure of these polynomials is closely tied with notions of discrete convexity, including matroids, submodular functions, and generalized permutohedra. I will discuss the beautiful real and combinatorial geometry underlying these polynomials and applications to matroid theory, including a proof of Mason’s conjecture on numbers of independent sets. This is based on joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.

(*Refreshments available at 2:30pm before the colloquium.*)