1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What do you mean by "the number of these series of ϵ net are unbounded"? $\endgroup$ Sep 10, 2012 at 4:01
  • $\begingroup$ It means that for example , it have a series of finite $/epsilon$ nets ,$A_i$' and the number of the element in $A_i$ are 5 ,8 ,100' ...., 10000,..... (not bounded). $\endgroup$ Sep 10, 2012 at 4:41
  • $\begingroup$ In its current form the question is not very clearly stated. When you ask for a uniform bound -- the word is "uniform", not "unique" -- are you allowing $\epsilon$ to vary? Are you asking about the cardinality of an $\epsilon$-net, or the number of possible $\epsilon$-nets for a given $\epsilon$? $\endgroup$
    – Yemon Choi
    Sep 10, 2012 at 7:34
  • $\begingroup$ Sorry for my poor explanation. The word "uniform" is best. The $\epsilon$ is fixed and given. And I also mean the cardinality of an $\epsilon$-net. $\endgroup$ Sep 10, 2012 at 7:54
  • $\begingroup$ I have rewote the statement. Thank you for Choi's recommendation. $\endgroup$ Sep 10, 2012 at 8:01

2 Answers 2

6
$\begingroup$

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|$.

$\endgroup$
1
  • $\begingroup$ I think you are right. It is the right answer for me, thanks. Nice trick. I have too limited reputation to vote you answer. Sorry. $\endgroup$ Sep 10, 2012 at 8:41
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You statement is right, however, I think there are some different between you statement and my question. In my question, the metric space and the $\epsilon$ is fixed. The only variable is the $\epsilon$-net. Sorry for my misleading question. I think i should rewote it again. $\endgroup$ Sep 10, 2012 at 8:28

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.