Follow

Flip graphs of matroids are expanders: gilkalai.wordpress.com/2018/12
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 arxiv.org/abs/1811.01816, via plus.google.com/11727145723611

Sign in to participate in the conversation
Mathstodon

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.