TY - GEN

T1 - Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes

AU - Bonnet, Gilles

AU - Dadush, Daniel

AU - Huiberts, Sophie

AU - Grupel, Uri

AU - Livshyts, Galyna

N1 - Funding Information:
Funding Gilles Bonnet: Funded by the DFG Priority Program (SPP) 2265 Random Geometric Systems, project P23. Daniel Dadush: Supported by the ERC Starting grant QIP–805241.
Publisher Copyright:
© Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts, and Galyna Livshyts; licensed under Creative Commons License CC-BY 4.0

PY - 2022/6/1

Y1 - 2022/6/1

N2 - 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 ?(nm n-1 1 ) and O(n2m n-1 1 + n54n) 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 1 T(n2m 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 n-1).

AB - 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 ?(nm n-1 1 ) and O(n2m n-1 1 + n54n) 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 1 T(n2m 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 n-1).

KW - Combinatorial Diameter

KW - Hirsch Conjecture

KW - Random Polytopes

UR - http://www.scopus.com/inward/record.url?scp=85134291247&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2022.18

DO - 10.4230/LIPIcs.SoCG.2022.18

M3 - Conference contribution

AN - SCOPUS:85134291247

VL - 224

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 18:1-18:15

BT - 38th Symposium on Computational Geometry (SoCG 2022)

A2 - Goaoc, Xavier

A2 - Kerber, Michael

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 38th International Symposium on Computational Geometry (SoCG 2022).

Y2 - 7 June 2022 through 10 June 2022

ER -