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

From papers

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.

Progress summary

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

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.