ACO The ACO Seminar (2018–2019)

May 9, 3:30pm, Wean 8220
Cynthia Vinzant, NC State University
Completely log-concave polynomials and matroids

Abstract:

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 inequalities on the numbers of independent sets and expansion of the edge graph of the matroid polytope. This is based on joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.


Back to the ACO home page