Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes

The combinatorial diameter diam(P) of a polytope P is the maximum shortest path distance between any pair of vertices, where length is measured by the number of edges in the path. 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 independent and identically distributed half-spaces whose supporting normals are chosen uniformly from the sphere, we show that diam(P) is Ω(nm1n-1) and O(n2m1n-1+n84n) with high probability when m≥2Ω(n).