2024/02/22 by Cardinal, Jean, Pournin, Lionel · 1 citation
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.2402.14343
The expansion of a polytope is an important parameter for the analysis of the random walks on its graph. A conjecture of Mihai and Vazirani states that all 0/1-polytopes have expansion at least 1. We show that the generalization to half-integral polytopes does not hold by constructing d-dimensional half-integral polytopes whose expansion decreases exponentially fast with d. We also prove that the expansion of half-integral zonotopes is uniformly bounded away from 0. As an intermediate result, we show that half-integral zonotopes are always graphical.