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

$\endgroup$
10
$\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).

$\endgroup$
  • $\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 Jul 28 '13 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 Jul 28 '13 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 Jul 28 '13 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 Jul 29 '13 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 Jul 29 '13 at 4:33

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.