Cynthia Vinzant : Matroids, log-concavity, and expanders (Feb 3, 2020 11:55 AM)

Matroids are combinatorial objects that model various types of independence. They appear several fields mathematics, including graph theory, combinatorial optimization, and algebraic geometry. In this talk, I will introduce the theory of matroids along with the closely related class of polynomials called strongly log-concave polynomials. Strong log-concavity is a functional property of a real multivariate polynomial that translates to useful conditions on its coefficients. Discrete probability distributions defined by these coefficients inherit several of these nice properties. I will discuss the beautiful real and combinatorial geometry underlying these polynomials and describe applications to random walks on the faces of simplicial complexes. Consequences include proofs of Mason's conjecture that the sequence of numbers of independent sets of a matroid is ultra log-concave and the Mihail-Vazirani conjecture that the basis exchange graph of a matroid has expansion at least one. This is based on joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.

• Category: Applied Math and Analysis
• Duration: 01:24:47
• Date:  February 3, 2020 at 11:55 AM
• Views: 214
• Tags:   seminar, Applied Math And Analysis Seminar