0
$\begingroup$

For any metric space $X$ and $\varepsilon>0$, let $$\text{cov}(X,\varepsilon)=\min\{n\,|\,X\text{ has a cover by }n\text{ many closed }\varepsilon\text{-balls}\},$$

be the ordinary covering numbers. For any $D>0$ and $N:(0,\infty)\rightarrow \mathbb{N}$, let $$U(D,N)=\{X\,|\,X\text{ is a compact metric space, diam}(X)\leq D,\,\text{cov}(X,\varepsilon)\leq N(\varepsilon)\},$$

be the set of compact metric spaces with uniformly bounded diameter and covering numbers. Gromov's compactness theorem implies that $U(D,N)$ is totally bounded with respect to the Gromov-Hausdorff distance for any $D$ and $N$, so in particular $\text{cov}_{GH}(U(D,N),\varepsilon)$ is always finite.

Are there any known bounds on $\text{cov}_{GH}(U(D,N),\varepsilon)$ in terms of $N$ (everything clearly scales with $D$, so setting $D=1$ is sufficient)?

$\endgroup$

1 Answer 1

1
$\begingroup$

Given a metric space $X$ with $\operatorname{cov}(X,\epsilon) \leq N(\epsilon)$, there exist $N(\epsilon_1)$ points such that each point is within $\epsilon_1$ of each of them. That set of $N(\epsilon_1)$ points is itself a metric space $Y$, with Gromov-Hausdorff distance at most $\epsilon_1$ to $X$. That metric space is determined by ${N(\epsilon_1) \choose 2}$ real numbers at most $D$. If we adjust each of these real numbers by at most $2\epsilon_2$, forming a metric space $Y'$, that represents a move of at most $\epsilon_2$ in Gromov-Hausdorff distance, since we can put a metric on $Y \cup Y'$ where the distance between a point in $Y$ and a point in $Y'$ is the average between the distance of the corresponding points in $Y$ and the distance of the corresponding points in $Y'$, plus $\epsilon_2$.

Let $Y'$ be $Y$ with all the distances rounded up to the nearest positive integer multiple of $2\epsilon_2$. This rounding process preserves the triangle inequality, because $\lceil a+b \rceil \leq \lceil a\rceil + \lceil b\rceil$, so we always obtain a metric space of distance $\leq \epsilon_2$ for $y$. There are $ \left\lceil \frac{D}{2 \epsilon_2} \right\rceil $ possible choices for each distance, so there are at most $\left\lceil \frac{D}{2 \epsilon_2} \right\rceil^{{N(\epsilon_1) \choose 2}}$ possible metric spaces $Y'$. This gives an $\epsilon_1+\epsilon_2$ covering, so the number of $\epsilon$-coverings is at most $$\min_{\epsilon_1+\epsilon_2=\epsilon} \left\lceil \frac{D}{2 \epsilon_2} \right\rceil^{{N(\epsilon_1) \choose 2}}$$

$\endgroup$
2
  • $\begingroup$ Great. This might be a much tougher question but do you have any idea how tight the bound is? $\endgroup$ Commented Dec 11, 2016 at 17:46
  • $\begingroup$ @Exomnium It might be hard to give lower bounds without an explicit function $N$. Is there a particular class of functions you're interested in (e.g. power laws?) $\endgroup$
    – Will Sawin
    Commented Dec 11, 2016 at 18:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .