A 20-year-old conjecture about the connectivity of high-dimensional shapes has finally been proven true.
April 23, 2026
Original Paper
The Mihail-Vazirani conjecture and strong edge-expansion in random 0/1 polytopes
arXiv · 2604.20589
The Takeaway
The Mihail-Vazirani conjecture holds for random 0/1 polytopes, revealing a dramatic phase transition in their edge expansion. At a specific probability threshold, the connectivity of these geometric objects changes fundamentally and abruptly. This proof provides a new understanding of how paths move through complex, multi-dimensional networks. Computer scientists can use this tipping point to better design algorithms for searching high-dimensional data. It shows that even the most abstract shapes have predictable breaking points.
From the abstract
We study the edge-expansion of the graph of a random $0/1$ polytope $P^d_p$, defined as the convex hull of a random subset of the points in $\{0,1\}^d$ where every point is retained independently and with probability $p$. This problem was introduced more than twenty years ago in a work of Gillmann and Kaibel, and has been extensively studied ever since.We prove that, for every fixed $\varepsilon>0$ and every $p\in(0,1-\varepsilon]$, with high probability the graph of $P^d_p$ has edge-expansion $