10
$\begingroup$

Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ with respect to the $l_1$ norm that have different radii and different centers. Is there an upper bound for the number of vertices that $B_1\cap B_2$ has?

$\endgroup$
1
  • 1
    $\begingroup$ It might be useful to determine the maximum number of vertices of the intersection of an $L_1$-ball and a halfspace, because such an intersection could be achieved by $B_1 \cap B_2$. So this would yield a lowerbound. Maybe $\Omega(n^2)$? $\endgroup$ Apr 3, 2015 at 1:18

1 Answer 1

9
$\begingroup$

There is an exponential upper bound of $9^n$, since every vertex of $B_1 \cap B_2$ is the intersection of a $k$-face of $B_1$ and a $(n-k)$-face of $B_2$ for some $k$, and the $\ell_1$-ball has $3^n$ faces (all dimensions counted together).

You cannot do better for large $n$ except for the value of the constant $9$. Indeed, let $B_1$ be $\ell_1$ ball of center $(\frac 1n,\cdots,\frac 1n)$ and radius $1$, and $B_2=-B_1$. Then $B_1 \cap B_2$ is the $(n-1)$-dimensional polytope defined as $$ \{ (x_1,\dots,x_n) \, : \, \sum x_i=0, \ |x_i| \leq 1/n \} .$$ If (for simplicity) $n$ is even, it has $\binom{n}{n/2} \geq (2-o(1))^n$ extreme points, namely those vectors with $|x_i|=1/n$ and evenly distributed signs.

Remarkably, with rotated balls centered at the origin, you get the same phenomenon. Indeed the intersection $K$ of the standard $\ell_1$ ball with a randomly rotated copy of itself has (with high probability) the property that $\frac{1}{\sqrt{n}} B \subset K \subset \frac{C}{\sqrt{n}} B$ for some constant $C$ (here $B$ is the Euclidean unit ball). This is known as the "global form of Kashin's theorem", see Theorem 5.5.4. in [1]. That sandwiching forces $K$ to have at least $\exp(cn)$ vertices for some other constant $c$ (essentially because a spherical cap of fixed angle less than $\pi/2$ covers an exponentially small proportion of the sphere as $n \to \infty$).

[1] S. Artstein-Avidan, A. Giannopoulos, V. Milman, Asymptotic Geometric Analysis, Part I

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.