Mihail–Vazirani conjecture on rapid mixing of the matroid basis-exchange walk
Mihail–Vazirani conjecture on rapid mixing of the matroid basis-exchange walk
Let be a matroid, and let its bases be its maximal independent sets. The base-exchange walk is the random walk on the bases of 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.