4
$\begingroup$

Let $(X,d)$ be a complete metric space and $n\in\mathbb N$. Suppose that every finite subset $F\subset X$ can be covered by $n$ closed balls of $X$ (that is, $N(Y,d,1)\le n$, in terms of covering numbers). Can $X$ itself be covered by $n$ closed balls? If not, what if $X$ is also assumed to be separable?

Some remarks

  • If $X$ is compact, it is true: $X$ is separable; if $S:=\{f_i\}_{i\ge1 }$ is dense in $X$ and for every $k$ $\displaystyle\{f_i\}_{1\le i\le k} \subset \bigcup_{1\le i\le n} \overline B(x_j^k,1)$, up to subsequences $(x_1^k,x_2^k,\dots,x_n^k)\to (x_1^\infty,x_2^\infty,\dots,x_n^\infty)\in X^n$ as $k\to\infty$, so $\displaystyle S\subset \bigcup_{1\le i\le n} \overline B(x_j^\infty,1) $ and then also $\displaystyle\overline S= X\subset \bigcup_{1\le i\le n} \overline B(x_j^\infty,1) $

  • If $X$ is not assumed to be complete, then it is not true in general: Here is an example: let $(e_i)_{i\ge1}$ be the standard Hilbert basis of $\ell_2$; let $u_i:=\frac1i\sum_{j=1}^ie_j$, let $X:=\{e_i\}_{i\ge1}\cup \{u_i\}_{i\ge1}\cup \{3ie_1\}_{1\le i< n}$, with the induced $\ell_2$ distance. Then we need $n-1$ unit balls to cover $\{3ie_1\}_{1\le i< n}$, and these balls are necessarily disjoint from the remaining points $\{e_i\}_{i\ge1}\cup \{u_i\}_{i\ge1}$, which however can’t be covered by a single unit closed ball centered at a point of $X$, because the only unit closed ball of $\ell_2$ containing every $e_i$ and every $u_i$ is the one centered at $0$, which is not in $X$.

  • If one uses open unit balls instead, in general it is false even for countable complete metric spaces: take the closure in $\ell_2$ of the preceding example, which is just $X\cup\{0\}$ (because $0=\lim_{i\to\infty}u_i$ is the only accumulation point of $X$). Then $X$ can’t be covered by $n$ open balls, fro the same argument.

$\endgroup$
2
  • 1
    $\begingroup$ Nice question! The closed balls I assume have fixed radius $1$? $\endgroup$ Commented Oct 17, 2024 at 13:04
  • $\begingroup$ Yep (or any fixed radius r). $\endgroup$ Commented Oct 17, 2024 at 16:06

1 Answer 1

5
$\begingroup$

We show that the conjecture is false. Given a connected graph $G$, we may always define a metric $d_G \colon G \times G \to [0, \infty)$ by

$$ d_G(x, y) = \inf \big\{ \operatorname{length}(\gamma) \mid \gamma \text{ is a path from } x \text{ to } y \big\}. $$

Moreover, $(G, d_G)$ is uniformly discrete and hence complete, and if $G$ is countable, then $G$ is separable. With this established, consider the graph on $\mathbb{Z} \times \mathbb{Z}$ where two points $(x, y)$ and $(x', y')$ are adjacent if and only if $(x - x')(y - y') > 0$.

If $S = \{(x_1, y_1), \ldots, (x_n, y_n)\} \subseteq G$ is finite, then $S \subseteq \overline{\!B}\big((1 + \max x_k, 1 + \max y_k); 1\big)$, since for all $j \in \{1, \ldots, n\}$, $$(1 + \max_{1 \leq k \leq n} x_k - x_j)(1 + \max_{1 \leq k \leq n} y_k - y_j) > 0. $$

However, given any finite collection of closed balls $\overline{\!B}\big((z_1, w_1); 1\big), \ldots, \overline{\!B}\big((z_m, w_m); 1\big)$, the point $(\min z_k, \max w_k)$ is not contained it its union, since for each $j \in \{1, \ldots, m\}$, $$ (z_j - \min_{1 \leq k \leq n} z_k)(w_j - \max_{1 \leq k \leq n} w_k) \leq 0. $$

$\endgroup$
4
  • $\begingroup$ Fantastic example! $\endgroup$ Commented Nov 3, 2024 at 6:00
  • $\begingroup$ Can we simply consider the following metric on non-zero integers: $d(x, -x)=2$, other distance are 1? Every finite set is covered by a ball of radius 1, but the whole space is not. $\endgroup$ Commented Nov 3, 2024 at 9:12
  • $\begingroup$ @FedorPetrov your proposal works but only disproves the $n = 1$ case. $\endgroup$ Commented Nov 3, 2024 at 10:08
  • 1
    $\begingroup$ Well, we may take Erdős-Rado universal graph, then every finite set is covered by a ball of radius 1 and no finite collection of such balls covers the whole space. But this is not easier construction than yours. $\endgroup$ Commented Nov 3, 2024 at 10:23

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.