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 $Ω(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^{Ω(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 $Θ(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 $Ω(m^{\frac{1}{n-1}})$.

Let$q\geq 2$be a prime power. In this paper, we study the distribution of the minimum distance (in the Hamming metric) of a random linear code of dimension$k$in$\mathbb {F}_{q}^{n}$. We provide quantitative estimates showing that the distribution function of the minimum distance is close (superpolynomiallyin$n$) to the cumulative distribution function of the minimum of$(q^{k}-1)/(q-1)$independent binomial random variables with parameters$\frac {1}{q}$and$n$. The latter, in turn, converges to a Gumbel distribution at integer points when$\frac {k}{n}$converges to a fixed number in (0, 1). Our result confirms in a strong sense that apart from identification of the weights of proportional codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimum code weight. As a corollary of the main result, we obtain an improvement of the Gilbert–Varshamov bound for$2< q< 49$.

In this paper, we study the distribution of the minimum distance (in the Hamming metric) of a random linear code of dimension k in $\mathbb{F}_q^n$. We provide quantitative estimates showing that the distribution function of the minimum distance is close (superpolynomially in n) to the cumulative distribution function of the minimum of (qk-1)/(q-1) independent binomial random variables with parameters $\frac{1}{q}$ and n. The latter, in turn, converges to a Gumbel distribution at integer points when $\frac{k}{n}$ converges to a fixed number in (0, 1). In a sense, our result shows that apart from identification of the weights of parallel codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimum code weight. As a corollary of the main result, we obtain an asymptotic improvement of the Gilbert-Varshamov bound for 2 < q < 49.

It was conjectured by Levi, Hadwiger, Gohberg and Markus that the boundary of any convex body in $${\mathbb R}^n$$ can be illuminated by at most $$2^n$$ light sources, and, moreover, $$2^n-1$$ light sources suffice unless the body is a parallelotope. We show that if a convex body is close to the cube in the Banach–Mazur metric, and it is not a parallelotope, then indeed $$2^n-1$$ light sources suffice to illuminate its boundary. Equivalently, any convex body sufficiently close to the cube, but not isometric to it, can be covered by $$2^n-1$$ smaller homothetic copies of itself.

In this note we study a conjecture of Madiman and Wang which predicted that the generalized Gaussian distribution minimizes the Rényi entropy of the sum of independent random variables. Through a variational analysis, we show that the generalized Gaussian fails to be a minimizer for the problem.