1
$\begingroup$

Let $(X,d)$ be a finite metric space. Clearly, $(X,d)$ is a doubling metric space but is there a 'best' estimate of $(X,d)$'s doubling constant?

Probability based on its cardinality, diameter, and minimum separation $\min_{x,y\in X\,x\neq y}\,d(x,y)$?

I'll recall some definitions to try and make the question self-contained.
Doubling constant The doubling constant of $(X,d)$ is the smallest $k>0$ such that, for every radius $r>0$ and each $x\in X$ there are at-most $k$ balls in $(X,d)$ of radius $r/2$ covering $\operatorname{Ball}(X,r)$

Doubling metric space: $(X,d)$ is doubling if it admits a finite doubling constant.

Improve this question
$\endgroup$
7
  • $\begingroup$ In what terms do you want an estimate? the best estimate of the doubling constant is the doubling constant itself. Are you asking an efficient algorithmic estimate? or an estimate in terms of other numerical values attached to $X$ (which ones?) $\endgroup$
    – YCor
    Commented Feb 2, 2022 at 11:52
  • $\begingroup$ @YCor I was looking for an estimate of $X$'s doubling constant in terms of the following numerical values: X's cardinality, its diameter, and the minimum separation $\min_{x,y;\,x\neq y}\,d(x,y)$. $\endgroup$
    – Carlos_Petterson
    Commented Feb 2, 2022 at 12:38
  • $\begingroup$ Fix arbitrary $D > \epsilon > 0$. Take $X = \{x_1, x_2,..., x_n\}$ such that $d(x_1, x_2) = \epsilon$ and all other distances to be $D$. It will have doubling constant of $(n-1)$ or $n$. The diameter will be $D$ and your $min = \epsilon$. $\endgroup$
    – Vladimir Zolotov
    Commented Feb 3, 2022 at 11:54
  • $\begingroup$ Also maybe you will be interested in KR-dimension. See the first page here: faculty.cc.gatech.edu/~isbell/reading/papers/… $\endgroup$
    – Vladimir Zolotov
    Commented Feb 3, 2022 at 12:02
  • $\begingroup$ @VladimirZolotov How does the KR-dimension differ from the Assoud (doubling) dimension? $\endgroup$
    – Carlos_Petterson
    Commented Feb 3, 2022 at 12:39

0

Reset to default

You must log in to answer this question.