11
$\begingroup$

For an $n$-element metric space $X=\{x_1,\dots,x_n\}$ with metric $d$ we introduce an array containing $\frac{n(n-1)}2$ numbers $d(x_i,x_j)$, $i<j$. We assume that all distances are at least $1$. The number of relevant scales for the metric space $X$ is defined as the number of intervals $[2^{i-1},2^{i})$ $i=1,2,\dots$ containing some elements of the array $d(x_i,x_j)$, $i<j$. Let $RS(n)$ be the maximal number of relevant scales which an $n$-element metric space may have.

Problems: (1) What is the rate of growth of $RS(n)$? (2) What about exact evaluation of $RS(n)$ for all $n\in \mathbb{N}$?

Comments: (1) In Exercise 3.37 of my book "Metric Embeddings" I suggest readers to prove the following two statements as exercises (hints are given):

(i) $RS(n)\ge 2n-3$.

(ii) $RS(n)\le \frac{n(n-1)}2-(n-4)$.

So for nontrivially large $n$ the number $RS(n)$ is strictly between $n$ and $\frac{n(n-1)}2$.

(2) One can replace $2$ by another number in the definition of $RS(n)$, and it may change the answer.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

First here is an $O(n\log n)$ upper bound. Make a complete graph whose vertex set is $X$ and the weights on its edges are the distances, $d(x_i,x_j)$. Consider a minimum weight spanning tree $T$ in this graph. Denote the weights/distances of the edges of the tree by $d_1,\ldots, d_{n-1}$. We claim that for every edgedistance $d$ of the graph we have an $i$ for which $d_i\le d\le (n-1)d_i$, which proves the upper bound.

For an edge $uv$ with weight $d$, take the path in $T$ between $u$ and $v$. Let the longest edge of this path be $d_i$. We have $d_i\le d$, otherwise replacing the edge of weight $d_i$ with $uv$ would give a spanning tree with a smaller weight. On the other hand, from the triangle inequality we have that $d$ is less than the sum of the weights of the edges of the path, which is at most $(n-1)d_i$.

Now, we can further improve this to $O(n)$ with a more detailed analysis, checking how the weights of the tree are distributed. This follows by applying the following lemma instead of the estimate of the previous paragraph.

Lemma. Denote by $RS'(n)$ the maximum possible number of intervals of the form $[2^k,2^{k-1})$ that contain at least one number of the form $x+\sum_{i\in I} d_i$ where $0\le x\le d_1$ and $\emptyset\ne I\subset \{1,\ldots,n\} $ and the maximum is taken over all $0\le d_1\le \ldots\le d_{n}$ numbers. Then $RS'(n)\le 2n$.

Proof. The proof is by induction. If for every $j$ we have $d_j\le d_1+\sum_{i<j} d_i$, then we have $d_j\le 2^{j-1} d_1$ and thus $\sum_j d_j\le (2^{n}-1)d_1$, so all the numbers of the form $x+\sum_{i\in I} d_i$ are between $d_1$ and $2^nd_1$, in this case $RS'(n)\le n+1$. On the other hand, if there is a $j$ for which $d_j> d_1+\sum_{i<j} d_i$, then divide the $d_i$ numbers into two groups, depending on whether their index is less than $j$ or not. For those whose index is less than $j$, by induction we have that they give at most $2j$ intervals. For those whose index is at least $j$, notice that we can again apply induction, since now $x$ ``grows'' to $d_j$ from $d_1$, so these give at most $2(n-j)$ intervals. In total we get at most $2n$ intervals, we are done.

Note that because we have changed $n-1$ to $n$ to make the lemma nicer, we got a $2n-2$ upper bound for the original problem, and if we remove the ``x'' from the lemma, then by induction we get an upper bound of $2n-3$, which matches the lower bound of (i).

Improve this answer
$\endgroup$
7
  • $\begingroup$ How do you apply the Lemma to the original problem? I assume that the set $I$ will end up being the collection of distances occurring along the tree between two points, but I don't see where the condition $0\le x \le d_1$ comes from. $\endgroup$
    – zeb
    Commented Jul 28, 2013 at 17:55
  • $\begingroup$ @zeb: It is not needed, its only there to make the induction work. That's why I said that for the original problem we would get 2n-3, since there we don't need the x. $\endgroup$
    – domotorp
    Commented Jul 28, 2013 at 19:08
  • $\begingroup$ In that case, it seems to me that there is an error - I see no reason for the shortest distance between two random points to actually be along the tree. I had thought your $x$ was somehow related to the path along the tree only giving an upper bound for the distances... $\endgroup$
    – zeb
    Commented Jul 28, 2013 at 22:37
  • $\begingroup$ @domotorp I enjoyed your answer and thanks for the correction. The correct answer is $2n-3$. Printing the question I miscomputed the outcome of the mentioned hint, which is: consider the weighted graph $K_{2,n-2}$ with the $2$-part labelled $a$ and $b$. Assign weights $2^2,2^4,\dots,2^{2(n-2)}$ for edges incident with $a$ and $2^2-\varepsilon,2^4-\varepsilon,\dots,2^{2(n-2)}-\varepsilon$ for edges incident with $b$, $0<\varepsilon\le 1$. Add an edge of length $1$ between $a$ and $b$. The metric corresponding to the obtained weighted graph has $2n-3$ relevant scales. $\endgroup$
    – Mikhail Ostrovskii
    Commented Jul 29, 2013 at 2:33
  • 1
    $\begingroup$ @zeb All distances of $X$ are contained in the intervals of the form $[2^k,2^{k+1})$ containing at least one number of the form $\sum_{i\in I} d_i$. In fact, for an edge $uv$ with weight $d$, take the path in $T$ between $u$ and $v$. Let $d_{i_1}\le\dots\le d_{i_k}$ be the weights of edges of this path. Then $d_{i_k}\le d\le \sum_{j=1}^kd_{i_k}$ as is explained. Binary intervals containing numbers $d_{i_k}, d_{i_k}+d_{i_{k-1}}, \dots, d_{i_k}+\dots+d_1$, form a sequence of consecutive binary intervals. No interval is missing because each next number is $\le$ twice the previous. $\endgroup$
    – Mikhail Ostrovskii
    Commented Jul 29, 2013 at 4:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .