Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Basis exchange walks on matroids are a class of Markov chains with many desirable properties: bounded spectral gap and modified log Sobolev constant, spectral independence, and fast mixing. These properties are also shared by another class of Markov chains: non-negatively curved Markov chains. We explore the following question: do all basis exchange walks exhibit non-negative curvature? Somewhat surprisingly, we find that the answer is no, giving examples of Markov chains that exhibit one local notion of expansion (spectral independence) but not another (non-negative curvature). We will prove a general curvature bound for basis exchange walks, provide explicit examples with negative curvature, and discuss several open questions this raises.