Mihail–Vazirani conjecture on edge-expansion of 0/1 polytopes
Let be a polytope, meaning the convex hull of a subset of the vertices of a hypercube, and let be its graph (the graph whose vertices are the vertices of and whose edges are its one-dimensional faces). Write for the edge-expansion of .
Mihail–Vazirani conjecture. Every polytope satisfies
High-dimensional hypercubes have edge-expansion by Harper's inequality, and this conjecture asserts that arbitrary polytopes expand at least as well. Its resolution status is not specified in the supplied text.
References
2 papers in this index state this conjecture (1999–2026). The statement above is taken from the most recent of them; the others are arXiv:math/9909177.
Source: Micha Christoph, Sahar Diskin, Lyuben Lichev and Benny Sudakov, “The Mihail-Vazirani conjecture and strong edge-expansion in random 0/1 polytopes”, arXiv:2604.20589 (2026).
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
No solutions have been posted yet.