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

For two points $x$, $y \in [0,1]^2$, let their distance be $d(x,y) := \|x-y\|_2^2$ (i.e. the usual distance, squared). Technically, this is a semimetric, as it does not satisfy the triangle inequality.

Given finite $P \subset [0,1]^2$, let $f(P)$ be the length (measured by $d$) of the minimal spanning tree of $P$. What is $\sup_{P \subset [0,1]^2} f(P)$?

A few words about my work so far: I am convinced that $\sup$ should be replaced by $\max$ and that it is 3. I am also convinced that $f$ is maximized by $S := \{(0,0),(0,1),(1,0), (1,1)\}$, uniquely. Given a point set $P$ and a minimal spanning tree, note that any two points $x,y \in P$ define a circle, with $\|x-y\|$ its diameter. If the edge $(x,y)$ is in the spanning tree, then adding a new point to $P$ within this circle creates a shortcut, reducing the size of the spanning tree. Adding a point $z$ on the circle changes nothing locally, as $d(x,y) = d(x,z) + d(z,y)$. Since the points in $S$ can never create a shortcut, $f(S \cup P) \geq f(P)$ for all $P$. Therefore, $$\sup_{P \subset [0,1]^2} f(P) \leq \sup_{P \subset [0,1]^2} f(P \cup S).$$

Unfortunately, the size of a minimal spanning tree is not monotonic. $f(S) = 3$, while $f(S \cup (0.5,0.5)) = 2$, but it is possible to add more points and again increase $f$.

This problem seems Putnam-esque, but I don't recall its origins. For all I know, it is open, but I would appreciate any thoughts on it.

share|improve this question
    
Can you show (or refute) that if P is a point set with a minimal spanning tree with a point p of degree 3, that P takeaway p gives a pointset with longer minimal spanning tree? Gerhard "Ask Me About System Design" Paseman, 2013.04.22 –  Gerhard Paseman Apr 22 '13 at 19:31
    
@Gerhard: not off the top of my head, but the situation I envision has this $p$ in the middle of 3 other points, and thus inside of some of the circles I was speaking about. That would imply that $p$ is a shortcut and removing it would increase $f(P)$. Basically, I don't know, but I will think about it. –  Eric Tressler Apr 22 '13 at 19:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.