Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes

Abstract

I will present a joint work (in progress) with Daniel Dadush, Uri Grupel, Sophie Huiberts and Galyna Livshyts. The combinatorial diameter $\text{diam}(P)$ of a polytope $P$ is the maximum shortest path distance between any pair of vertices. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random “spherical” polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an $n$-dimensional polytope $P$ defined by the intersection of$m$ i.i.d.\ half-spaces whose normals are chosen uniformly from the sphere,we show that $\text{diam}(P)$ is $\mathrm{\Omega }(n{m}^{\frac{1}{n-1}})$ and $O(n^2{m}^{\frac{1}{n-1}}+n^5{4}^n)$ with high probability when $m\ge 2^{\mathrm{\Omega }(n)}$. For the upper bound, we first prove that the number of vertices in any fixed two-dimensional projection sharply concentrates around its expectation when$m$ is large, where we rely on the $\mathrm{\Theta }(n^2{m}^{\frac{1}{n-1}})$ bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these “shadows paths” together over a suitable net using worst-case diameter bounds to connect vertices to the nearest shadow. For the lower bound, we first reduce to lower bounding the diameter of the dual polytope $P^{\circ }$, corresponding to a random convex hull, by showing the relation $\text{diam}(P)\ge (n-1)(\text{diam}(P^{\circ })-2)$. We then prove that the shortest path between any “nearly” antipodal pair vertices of $P^{\circ }$ has length $\mathrm{\Omega }(m^{\frac{1}{n-1}})$.