Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
What do you mean by "the number of these series of ϵ net are unbounded"? –  Trevor Wilson Sep 10 '12 at 4:01
    
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). –  Zhongmin Jin Sep 10 '12 at 4:41
    
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$? –  Yemon Choi Sep 10 '12 at 7:34
    
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. –  Zhongmin Jin Sep 10 '12 at 7:54
    
I have rewote the statement. Thank you for Choi's recommendation. –  Zhongmin Jin Sep 10 '12 at 8:01
add comment

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
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. –  Zhongmin Jin Sep 10 '12 at 8:41
add comment

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.

share|improve this answer
    
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. –  Zhongmin Jin Sep 10 '12 at 8:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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