## Seminars

## Seminars

## Probability and Statistics Seminar——Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes

**Holder：** Gilles Bonnet (University of Groningen)

**Time：**2022-05-23 14:00-15:00

**Location：**Zoom Meeting（824 6651 1571）

**Abstract: **
The combinatorial diameter $\operatorname{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 $\operatorname{diam}(P)$ is $\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 \geq 2^{\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 $\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 $\operatorname{diam}(P) \geq (n-1)(\operatorname{diam}(P^\circ)-2)$. We then prove that the shortest path between any ``nearly'' antipodal pair vertices of $P^\circ$ has length $\Omega(m^{\frac{1}{n-1}})$.

This is a joint work with Daniel Dadush, Uri Grupel, Sophie Huiberts and Galyna Livshyts, see https://arxiv.org/abs/2112.13027.

**About the Speaker: **

G.F.Y. (Gilles) Bonnet, Dr

Field/Discipline: Mathematics

Expertise: Probability theory, Stochastic Geometry, Integral Geometry

Homepage: *https://www.rug.nl/staff/g.f.y.bonnet/*

Zoom: *https://zoom.us/j/82466511571?pwd="2ZFDSjkYSJZCB9dTaq1irS708fe8wM.1*

ID: 824 6651 1571

Password: 955350

**Your participation is warmly welcomed! **

**欢迎扫码关注北大统计科学中心公众号，了解更多讲座信息！ **