Flip graphs of matroids are expanders: https://gilkalai.wordpress.com/2018/12/12/nima-anari-kuikui-liu-shayan-oveis-gharan-and-cynthia-vinzant-solved-the-mihail-vazirani-conjecture/
+Gil Kalai reports on a new proof by Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant of a conjecture by Milena Mihail and Umesh Vazirani that any subset S of at most half of the bases of a matroid has at least |S| flips to a base outside S.

Based on a preprint at https://arxiv.org/abs/1811.01816. Via https://plus.google.com/117271457236114081433/posts/BBWDnosHkqy but reposted directly rather than reshared in order to get the image to show the correct Vazirani.
Shared publiclyView activity