Mihail–Vazirani conjecture on rapid mixing of the matroid basis-exchange walk

Let M=(X,I)M=(X,\mathcal{I}) be a matroid, and let its bases be its maximal independent sets. The base-exchange walk is the random walk on the bases of MM that removes a uniformly chosen element from the current base and then chooses a new base containing the resulting independent set. Mihail–Vazirani conjecture. The base-exchange walk converges rapidly. The paper explicitly states that Anari, Liu, Gharan, and Vinzant resolved this conjecture using rapid convergence of the down-up walk on local spectral expanders, so the conjecture is solved.

Sources & referencesView supporting material

Primary source

Roy Gotlib and Tali Kaufman, “No Where to Go But High: A Perspective on High Dimensional Expanders”, arXiv:2304.10106 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.