2
$\begingroup$

The recent question "Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell" can be restated in terms of "minimum spanning trees intersecting each (closed) lattice square of an $n\times n$ lattice".

I am wondering whether there is a substantial change if we require the trees to intersect every axis-parallel unit square contained in the big $n\times n$ square, not only lattice squares. Note that in both examples of the other thread, much bigger squares can be squeezed between the branches without intersecting them.

If we denote by $a(n)$ the minimal length of such a tree in the original question and by $b(n)$ the minimal length in the modified question, we have obviously $a(n)\le b(n)$. For $n=2^k+1$, we have $b(n)\le\dfrac{4^k-1}3(\sqrt{3}+1)$, and I would think intuitively that this inequality is sharp.

Can it be shown that $b(2^k+1)=\dfrac{4^k-1}3(\sqrt{3}+1)$?

The construction achieving that has a 'base tree' (i.e. one of the two minimal Steiner trees connecting the 4 unit square corners) in each square $(i,j)$ which has $\nu_2(i)=\nu_2(j)$. Here $0<i,j<2^k$ and $\nu_2(\cdot)$ is the 2-adic exponent, e.g. for $k=3$, the pattern in the $9\times9$ square is

X   X   X   X 
  X       X
X   X   X   X 
      X     
X   X   X   X 
  X       X
X   X   X   X 

where each 'X' denotes a base tree, so diagonally adjacent such cells have a common vertice. (Think of the space-filling "X-fractal" obtained by iterating this pattern in the obvious way.) Such a tree contains each lattice point, i.e. all corners of the $n\times n$ lattice squares, thus it intersects each unit square.

Likewise: Can it be shown that $a(2^{k+1})=2\dfrac{4^k-1}3(\sqrt{3}+1)$, using the same pattern but with the base trees twice as large?

I have no idea if for $k=2$ the $b(5)$ tree has a bigger length than the $n=5$ "candidate" given in the other thread. Probably it has, so:

Is it true that for all $n\ge4$, $a(n)< b(n)$? What about $\lim\limits_{n\to\infty}\dfrac{a(n)}{b(n)}$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.