2021/12/24 by Bonnet, Gilles, Dadush, Daniel, Grupel, Uri +2
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Control (math.OC) #Probability (math.PR)
paper · doi:10.48550/arxiv.2112.13027
The combinatorial diameter 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 diam(P) is Ω(n m(1)/(n-1)) and O(n2 m(1)/(n-1) + n5 4n) with high probability when m ≥ 2Ω(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 Θ(n2 m(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^∘, corresponding to a random convex hull, by showing the relation diam(P) ≥ (n-1)(diam(P^∘)-2). We then prove that the shortest path between any ``nearly'' antipodal pair vertices of P^∘ has length Ω(m(1)/(n-1)).