Mihail–Vazirani conjecture on edge-expansion of 0/1 polytopes
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.