2025/09/11 by Ferber, Asaf, Krivelevich, Michael, Sales, Marcelo +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.09831
A 0/1-polytope in ℝn is the convex hull of a subset of \0,1\n. The graph of a polytope P is the graph whose vertices are the zero-dimensional faces of P and whose edges are the one-dimensional faces of P. A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every 0/1-polytope is at least one. We study a random version of the problem, where the polytope is generated by selecting vertices of \0,1\n independently at random with probability p∈ (0,1). Improving earlier results, we show that, for any p∈ (0,1), with high probability the edge expansion of the random 0/1-polytope is bounded from below by an absolute constant.