We prove bounds of order $n^{n/2}e^{O(n)}$ for the expected number of facets of high-dimensional random polytopes. First, let $\mu$ be a non-degenerate compactly supported even probability measure on $\R$ satisfying $\mu([x^\ast-s,x^\ast])\asymp s^\kappa$ near its right endpoint $x^\ast$. For every sufficiently small fixed $\alpha>0$, the convex hull of $N=\lfloor e^{\alpha n}\rfloor$ independent points with law $\mu^{\otimes n}$ has at least $n^{n/2}e^{-C_{\mu,\alpha}n}$ expected facets; this includes all symmetric finite-alphabet distributions. For every full-dimensional log-concave probability measure on $\R^n$, we prove that there exist $T\in[n,2n]$ and $N=\lceil e^Tn^{3/2}\rceil$ for which \[ n^{n/2}e^{-Cn} \leq \mathbb E f_{n-1}(P_N) \leq n^{n/2}e^{Cn}. \] Thus the scale $n^{n/2}$, up to exponential factors, is universal for log-concave measures in this high-dimensional exponential regime. Finally, we construct a symmetric isotropic full-support non-log-concave counterexample with only $(1+o(1))2^n$ expected facets.
We show that every polytope $P\subseteq[0,1]^n$, and more generally every compact convex set, has Chv\'atal rank at most $12.22n^2+n\log_2 n+2n+4$. This improves the $O(n^2\log n)$ bound of Eisenbrand and Schulz and, together with the $\Omega(n^2)$ lower bound of Rothvo{\ss} and Sanit\`a, shows that the maximum Chv\'at...
Let $W=n^{-1/2}\sum_{i=1}^n X_i$, where the $X_i$ are independent centered random vectors in ${\mathbb R}^p$ with $|X_{ij}|\le B$ almost surely. Suppose that $\text{Cov}(W)$ has unit diagonal and smallest eigenvalue at least $b^2>0$. We prove that the distance between $W$ and a Gaussian vector with the same covariance,...
Let $\delta>0$ be fixed, let $m = \lceil(1+\delta)n\rceil$, and let $\Gamma$ be an $n\times m$ matrix with independent standard Gaussian entries. For the Gaussian Gluskin polytope $G_m = \Gamma(B_1^m)$ we prove $$ \p\left\{d_{\mathrm{BM}}(G_m,B_1^n) \ge c_\delta n^{5/8}(\log n)^{-1/8}\right\} \ge 1-Ce^{-cn}. $$ Consequ...
Let $d,K,N\in \mathbb{N}$ with $K\geq 3$ and $d\geq 4K+4$. Let $\Delta\subset \mathbb{Z}^d$ be the vertex set of a nondegenerate $(K-1)$-simplex, and let $A\subseteq[N]^d$ contain no nontrivial similar copy of $\Delta$. We prove that \[ |A|\ll_{\Delta,d} N^d\exp\!\left(-c_{\Delta,d}\sqrt{\log N}\right) \] improving upo...
Andrew Lott, Á. Magyar, N. R. Ponagandla· 0 citations
Let $k_{1,\varepsilon}(n)$ be the smallest number of real linear measurements needed by a randomized oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pm\varepsilon$, with probability at least $2/3$. For every fixed $0<\varepsilon<1$, we prove \[ \frac{n^2}{(\log...
Let $q(n)$ denote the total number of partitions of $n$ into distinct parts and $\Delta$ be the difference operator with respect to $n$. We prove that for any real number $\alpha$, there exists an integer $n(\alpha)$ such that the sequence\ $\{\sqrt[n]{q(n)/n^{\alpha } } \}_{n\ge n(\alpha) } $ is log-convex by obtainin...
Hui Guo, Zuo-Ru Zhang· Electronic Journal of Combin...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
