a question about $\epsilon$ net of a compact metric space. - MathOverflow

a question about $\epsilon$ net of a compact metric space.

2012-09-10T03:54:55Z

A subset A of a compact metric M is called a $\epsilon$ net if it satisfies the following conditions

(1)$\epsilon$ dense: the neighborhood of A is the entire M

(2)$\epsilon$ separate: $\forall x, y \in A$, $d(x,y)>\epsilon$

It is a well known fact that for any $\epsilon$, there is a fintie $\epsilon$ net.

And I wonder whether there is an uniform bound for cardinalities of all the $\epsilon$-nets of a given compact metric space(fixed $\epsilon$). May be exist a comapcat metric space,just constructing one, who have a series of $\epsilon$ net and the cardinality of these series of $\epsilon$ net are unbounded.

I think the question is negative and should involve the Hausdorff measure, dimenson and volume, but now I am confused. It will be so nice for some people to give me a answer.

Answer by anton for a question about $\epsilon$ net of a compact metric space.

2012-09-10T08:13:12Z

I interprete the universality as follows: For given $\epsilon$, is there a natural number $N=N_\epsilon$ such that for all compact metric spaces $K$ of diameter $\le 1$ there exists an $\epsilon$-net of cardinality $\le N$. The bound on the diameter is necessary, for otherwise compact intervals in $\mathbb R$ would give counterexamples.

The answer is no: Let $I=[0,1]$ be the unit interval. On the set $I^n$ instal the metric attached to the norm $$ ||a||=\max_j|a_j|. $$ Then $I^n$ has diameter $1$. For $\epsilon=1/4$ an $\epsilon$-ball in $I^n$ has at most euclidean volume $1/2^n$, therefore you need at least $2^n$ such balls to cover $I^n$ which has euclidean volume 1.

Answer by Sean Eberhard for a question about $\epsilon$ net of a compact metric space.

2012-09-10T08:29:28Z

Are you asking whether there is always an upper bound on the cardinality of an $\epsilon$-separated set of points in a compact metric space $X$? If so, the answer is yes.

Find a finite $\epsilon/2$-net $N$. Let $S$ be an $\epsilon$-separated set of points. Then every point of $S$ is in $B_{\epsilon/2}(x)$ for some $x\in N$, and no two points of $S$ lie in the same $B_{\epsilon/2}(x)$, so $|S|\leq |N|$.