Timeline for The number of relevant scales for a finite metric space
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29, 2013 at 9:32 | comment | added | domotorp | @Mikhail: Thanks. In fact I think by induction it is also easy to give a $2n-3$ example in $\mathbb R$. Just start with $0$ and $1$, then in each step add $2^{2i}$, similarly as in your example. | |
| Jul 29, 2013 at 9:28 | history | edited | domotorp | CC BY-SA 3.0 |
deleted 316 characters in body
|
| Jul 29, 2013 at 4:44 | comment | added | zeb | Oh, I see now. That is awfully clever. | |
| Jul 29, 2013 at 4:33 | comment | added | Mikhail Ostrovskii | @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. | |
| Jul 29, 2013 at 2:38 | vote | accept | Mikhail Ostrovskii | ||
| Jul 29, 2013 at 2:33 | comment | added | Mikhail Ostrovskii | @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. | |
| Jul 28, 2013 at 22:37 | comment | added | zeb | 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... | |
| Jul 28, 2013 at 19:08 | comment | added | domotorp | @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. | |
| Jul 28, 2013 at 17:55 | comment | added | zeb | 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. | |
| Jul 28, 2013 at 12:31 | history | edited | domotorp | CC BY-SA 3.0 |
added 267 characters in body
|
| Jul 28, 2013 at 10:00 | history | edited | domotorp | CC BY-SA 3.0 |
added 1113 characters in body
|
| Jul 28, 2013 at 9:48 | history | edited | domotorp | CC BY-SA 3.0 |
added 1113 characters in body
|
| Jul 28, 2013 at 7:27 | history | edited | domotorp | CC BY-SA 3.0 |
added 182 characters in body
|
| Jul 28, 2013 at 7:09 | history | answered | domotorp | CC BY-SA 3.0 |