Skip to content
DraconiticResearch
Search Sources API
201,642 studies31 sourcesUpdated 15 min ago
PreprintCC BY 4.0arXiv

0/1-Polytopes with Exponentially Small Edge Expansion

  • Xiongxin Yang
Open at sourcePDFDOICite

Abstract

We present a simple construction of a family of 0/1-polytopes whose edge expansion decreases exponentially with the dimension, which disproves the Mihail-Vazirani conjecture that the graph of every 0/1-polytope has edge expansion at least one.

Related

  1. Mixed partition functions are exactly the graph parameters of exponentially bounded edge-connection rank
    William Whistler
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. Bounded powers of edge ideals: Nearly Gorenstein polytopes
    Takayuki Hibi, Seyed Amin Seyed Fakhari
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. A refinement of the edge theorem for order and chain polytopes
    Jon Lee
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Asymptotic expansion of the voltage potential under small Robin perturbations of its boundary conditions
    Charles Dapogny, Eric Bonnetier, Roman Moskalenko
    HALPreprintCC BY 4.0Full textOptimisation & controlHAL
  5. Asymptotic expansion of the voltage potential under small Robin perturbations of its boundary conditions
    Eric Bonnetier, Charles Dapogny, Roman Moskalenko
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yang202601polytopes,
  title = {{$0/1$-Polytopes with Exponentially Small Edge Expansion}},
  author = {Xiongxin Yang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2608.01870},
  eprint = {2608.01870},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.01870},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - 0/1-Polytopes with Exponentially Small Edge Expansion
AU  - Xiongxin Yang
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2608.01870
UR  - https://arxiv.org/abs/2608.01870
AB  - We present a simple construction of a family of 0/1-polytopes whose edge expansion decreases exponentially with the dimension, which disproves the Mihail-Vazirani conjecture that the graph of every 0/1-polytope has edge expansion at least one.
ER  -