The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes
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 $Θ(d)$. This improves the previously best known bound due to Ferber, Krivelevich, Sales and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.20589
curl -X POST /api/v1/records/arxiv/2604.20589/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.20589/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'