On the Many Faces of Easily Covered Polytopes
| Autor: | Florentin, Dan I., Milo, Tomer |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Assume that $rB_{2}^{n} \subset P$ for some polytope $P \subset \mathbb{R}^n$, where $r \in (\frac{1}{2},1]$. Denote by $\mathcal{F}$ the set of facets of $P$, and by $N=N(P,B_2^n)$ the covering number of $P$ by the Euclidean unit ball $B_2^n$. We prove that if $\log N \le\frac{n}{8}$, then \[ |\mathcal{F}| \ge \left( \frac{1}{ 2\left(1 - r \sqrt{1-\frac{4\log N}{n}}\right) } \right)^{\frac{n-1}{2}}. \] Comment: 7 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|