The combinatorial diameter <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\operatorname {diam}(P)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>diam</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\operatorname {diam}(P)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>diam</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Omega (n m^{\frac{1}{n-1}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <msup> <mi>m</mi> <mfrac> <mn>1</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(n^2 m^{\frac{1}{n-1}} + n^8 4^n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <msup> <mi>m</mi> <mfrac> <mn>1</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </msup> <mo>+</mo> <msup> <mi>n</mi> <mn>8</mn> </msup> <msup> <mn>4</mn> <mi>n</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with high probability when <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$m \ge 2^{\Omega (n)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <msup> <mn>2</mn> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>.

Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes

期刊论文
发表日期：

2026年2月3日

查看全文

Gilles Bonnet,
Daniel Dadush,
Uri Grupel,
Sophie Huiberts,
Galyna Livshyts

摘要

The combinatorial diameter $\operatorname {diam}(P)$ $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 $\operatorname {diam}(P)$ $diam (P)$ is $\Omega (n m^{\frac{1}{n-1}})$ $Ω (n m^{\frac{1}{n - 1}})$ and $O(n^2 m^{\frac{1}{n-1}} + n^8 4^n)$ $O (n^{2} m^{\frac{1}{n - 1}} + n^{8} 4^{n})$ with high probability when $m \ge 2^{\Omega (n)}$ $m \geq 2^{Ω (n)}$ .