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

Let S be any compact and denumerably infinite metric space and let d be the metric of S. We shall say that S satisfies condition C, if there exists at least one infinite sequence-------------p(1),p(2),.....,p(n),....of points of S such that (1) each point of S occurs once and only once in the sequence (2) the series d(p(1),p(2))+d(p(2),p(3))+.....+d(p(n),p(n+1))+....is convergent. If S satisfies condition C, an infinite version of the travelling salesman problem can be posed for the points of S. S always contains at least one limit point, since otherwise it could be covered by an infinite set of pairwise disjoint open balls, each containing a point of S-an impossibility if S is compact. It is easy to show that S cannot satisfy condition C if it contains more than one limit point. My question is: If S contains one and only one limit point, does S then necessarily always satisfy condition C?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

Let the space consist of a point $P$ and infinitely many other points $Q_n$ for $n\in\mathbb N$. Let the distance from $P$ to $Q_n$ be $1/n$. Let the distance from $Q_n$ to $Q_m$ for $m\neq n$ be $(1/n)+(1/m)$. This seems to be a counterexample for your question.

share|improve this answer
    
Thanks Andreas, that is really very nice. Any infinite sequence in which each point of your space occurs at least once generates a series that grows faster (term by term) than some permutation of the Harmonic Series. Your metric space is certainly exotic. If n is any integer greater than 1, the point Q(n) is always "collinear with" the points Q(1) and p while p always lies "between" Q(1) and Q(n) on this "straight line". Could your space be isometrically embedded in any finite dimensional Euclidean space or even Hilbert space? I wonder whether there are any less exotic counterexamples. –  Garabed Gulbenkian Sep 27 '13 at 17:23
    
@GarabedGulbenkian I think your comment about collinearity almost proves that the space I suggested can't be embedded in Hilbert space. The straight line through Q(1) and P would have to contain all of the Q(n)'s, and every two of these would have to lie on opposite sides of P. But that's impossible, as there are only two sides of P on a line and we need infinitely many sides to accommodate all the Q(n)'s. –  Andreas Blass Sep 28 '13 at 12:57
    
Yes, that shows that your metric space is truly exotic. I tried, with no success, to find, some subsets of the Euclidean plane which I could prove to be counterexamples. Nor was I able to prove that such planar counterexamples could not exist. But your comment is also a proof that no subsets of the Euclidean straight line can be counterexamples. –  Garabed Gulbenkian Sep 28 '13 at 18:20

The countable compact subspace $\ S:=\{q_0\ q_1\ \ldots\}\subseteq\ell^2\ $ of Hilbert space $\ \ell^2,\ $ given below, fails to have property C, i.e. it cannot be travelled along any finite length path (condition C was defined in the Question above):

  • $q_0 := \mathbb 0\in \ell^2$
  • $q_n\ $ has all coordinates $\ 0\ $ except for the $n$-th coordinate equal $\ \frac 1n\ $ for every $\ n=1\ 2\ \ldots$.

Now let $\ (p_1\ p_2\ \ldots)\ $ be a sequence of points of $\ S,\ $ in which each point $\ q_k\ $appears exactly one time. We will see that this routing path has infinite length:

$$\sum_{k=2}^\infty ||p_k-p_{k-1}||\ =\ \infty$$

PROOF

For each natural $\ M\ $ there exists natural $\ n\ $ such that

$$\{p_1\ \ldots\ p_n\}\ \supseteq\ \{q_1\ \ldots\ q_M\}$$

Let's use the following inequality:

$$\forall_{a\ b\in\ell^2}\quad \left(\ a\cdot b = 0\quad\Rightarrow\quad ||a-b||\ \ge\ \frac{||a||}{\surd 2}\ +\ \frac{||b||}{\surd 2}\ \right)$$

Thus:

$$\sum_{k=2}^n ||p_k-p_{k-1}||\ \ge\ \frac 1{\surd 2}\cdot\sum_{k=2}^n \left(||p_{k-1}||+||p_k||\right)\ =\ \surd 2\cdot\sum_{k=1}^n ||p_k||\ -\ \frac 1{\surd 2}\cdot\left(||p_1||+||p_n||\right)$$

hence

$$\sum_{k=2}^n ||p_k-p_{k-1}||\ \ge\ \surd 2\cdot\sum_{k=1}^M ||q_k||\ -\ \frac 1{\surd 2}\cdot\left(\frac 11+\frac 12\right) $$

and finally:

$$\sum_{k=2}^n ||p_k-p_{k-1}||\ \ \ge\ \ \surd 2\cdot\log(M+1)\ -\ \frac{3\cdot\surd 2}4\quad\longrightarrow\quad\infty$$

for $\ M\rightarrow\infty\ $ (where $\ n\ $ depends on $\ M$)   END of PROOF


REMARK   @Andreas has provided an example which cannot be embedded isometrically into any Hilbert space (but I would never dream to call it exotic :-). Thus I decided to provide one in the Hilbert space $\ \ell^2$. Now harder work can start.

share|improve this answer

I'll show a counterexample in Euclidean $\ (\mathbb R^2\ \,d)$:

THEOREM There exists a countable compact $\ X\subseteq\mathbb R^2,\ $ which has exactly one limit point (hence $\ X\ $ is infinite), and such that every route $\ (p(1)\ p(2)\ \ldots)\ $ of $\ X\ $ has infinite length.

Here we understand that $\ (p(1)\ p(2)\ \ldots)\ $ being a route of $\ X\ $ means that all points $\ p(t)\ $ are different, and

$$ \{p(1)\ p(2)\ \ldots\}\ =\ X$$

and the length of such route is $\ \sum_{k=1}^\infty d(p(k)\ p(k+1))$.

PROOF   Let $\ O:=(0\ 0)\in\mathbb R^2.\ $ Let variables $\ k\ n\ $ run only through natural numbers $\ 1\ 2\ \ldots\ .\ $ Define

$$ X\ :=\ \{O\}\ \cup\ \left\{(\frac 1k\ \frac 1n)\ :\ \max(k\ n)\le 2\cdot\min(k\ n)\right\} $$

Consider $\ \ \delta(x) := \min_{y\in X\setminus\{x\}} d(x\ y)\ \ $ for every $\ x\in\mathbb R^2\setminus\{O\}.\ $ This minimum is well defined and satisfies:

$$ \delta\left(\left(\frac 1k \frac 1n\right)\right)\ \ge\ \frac 1{\max(k\ n)\cdot(\max(k\ n)+1)}$$

There are exactly $\ 2\cdot n+1\ $ points $\ \left(\frac 1r\ \frac 1s\right)\in X\ $ such that $\ \min(r\ s) = n.\ $ For each $\ 2\cdot n+1\ $ of such points $\ x\ $ we have $\ \delta(x)\ge \frac 1{2\cdot n\cdot(2\cdot n+1)}.\ $

Now consider an arbitrary route $\ (p(1)\ p(2)\ \ldots)\ $ of $\ X.\ $ For each of the $\ 2\cdot n+1\ $ points $\ p(t)\ $ such that it is one of points $\ x\ $ from above, we get:

$$ d(p(t)\ p(t+1))\ \ge\ \frac 1{2\cdot n\cdot(2\cdot n+1)}$$

Thus the sum of these $\ 2\cdot n + 1\ $ distances is at least $\ \frac 1{2\cdot n}.\ $ Thus (with a harmless abuse of notation):

$$\sum_{t=1}^\infty d(p(t)\ p(p(t+1))\ \gt \sum_{n=1}^\infty \frac 1{2\cdot n}\ \ge\ \infty$$

END of PROOF

share|improve this answer

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.