Mihail–Vazirani conjecture on edge-expansion of 0/1 polytopes

About 27 years old · traced to

Let PP be a 0/10/1 polytope, meaning the convex hull of a subset of the vertices of a hypercube, and let GPG_P be its graph (the graph whose vertices are the vertices of PP and whose edges are its one-dimensional faces). Write h(GP)h(G_P) for the edge-expansion of GPG_P.

Mihail–Vazirani conjecture. Every 0/10/1 polytope PP satisfies

h(GP)≥1.h(G_P) \ge 1.

High-dimensional hypercubes have edge-expansion 11 by Harper's inequality, and this conjecture asserts that arbitrary 0/10/1 polytopes expand at least as well. Its resolution status is not specified in the supplied text.

References

Primary 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).

Additional 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.

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.