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.

  • $\begingroup$ What do you mean by "the number of these series of ϵ net are unbounded"? $\endgroup$ – Trevor Wilson Sep 10 '12 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$ – Zhongmin Jin Sep 10 '12 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 '12 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$ – Zhongmin Jin Sep 10 '12 at 7:54
  • $\begingroup$ I have rewote the statement. Thank you for Choi's recommendation. $\endgroup$ – Zhongmin Jin Sep 10 '12 at 8:01

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

| cite | improve this answer | |
  • $\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$ – Zhongmin Jin Sep 10 '12 at 8:41

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.

| cite | improve this answer | |
  • $\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$ – Zhongmin Jin Sep 10 '12 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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