Timeline for Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree
Current License: CC BY-SA 4.0
37 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 13 at 2:42 | vote | accept | Marco Ripà | ||
| Jun 11 at 16:46 | comment | added | Peter Taylor | @DavidESpeyer, I managed to reproduce Bridges' value for 3D about the same time that Emil posted it above, and I noticed visually that the 2D projection matches the 2D solution. Obviously since the three edges around a Steiner point are coplanar, if you look parallel to the plane they project to a line. That's about as much intuition as I had: the rest was calculation up to 6D to sanity-check that it gave something reasonable. | |
| Jun 11 at 15:56 | comment | added | David E Speyer | @PeterTaylor You are onto something. It does seem that we can build the $k$-dimensional solution from the $k-1$ dimensional solution by (1) embedding the $k-1$ dimensional solution in the plane $z_k=0$, through the center of the cube and (2) for each edge from an internal vertex $v$ to a leaf $x$, introducing a new vertex at the isogonal point of $(v,0)$, $(x,-1)$ and $(x,1)$ and joining it in the obvious way. It wasn't clear to me that this should happen until I solved the linear equations in my answer; do you have a more direct intuition? | |
| Jun 11 at 15:41 | answer | added | David E Speyer | timeline score: 9 | |
| Jun 11 at 14:40 | comment | added | Peter Taylor | Using the recursive construction of my previous comment it appears that $l_{min}(k) \le 1 + (2^{k-1}-1)\sqrt 3$. | |
| Jun 11 at 14:02 | comment | added | David E Speyer | I figured out how to get $1+3 \sqrt{3}$. (Except that I used a cube of side length $2$, so I got $2+6 \sqrt{3}$). Let $r_1 = 1-1/\sqrt{3}$, $r_2 = 1/\sqrt{3}$, $r_3 = 2 /\sqrt{3}$; let $u_1 = (1,0,0)$, $u_2 = (1/2, \sqrt{3}/2,0)$, $u_3 = (1/4, \sqrt{3}/2, \sqrt{3}/2)$. Then three of the vertices are at $r_1 u_1=(1-1/\sqrt{3},0,0)$, $r_1 u_1 + r_2 u_2=(1-1/(2\sqrt{3}),1/2,0)$ and $r_1 u_1 + r_2 u_2 +r_3 u_3 = (1,1,1)$, and the other vertices are gotten by changing the signs of coordinates. The total length is $2 r1 + 4 r2 + 8 r3 = 2+6\sqrt{3}$. | |
| Jun 11 at 13:34 | comment | added | Peter Taylor | @DavidESpeyer, by analogy with the extension from 2D to 3D it seems that you might be able to lift dimensions easily enough. If $P_{k,i}$ are the vertices of the solution in $k$ dimensions, translate to coordinate $\tfrac 12$ in the $(k+1)$th dimension and turn each edge to a leaf $(\vec{v}, \tfrac 12)$ into a fork which covers $(\vec{v}, \tfrac 12 \pm \tfrac 12)$ by finding the isogonal point. | |
| Jun 11 at 13:21 | comment | added | Marco Ripà | About the mentioned Bridges' paper, I wonder whether or not we have the exact formula for that sub $6.2$ value (I cannot read the full text right now). | |
| Jun 11 at 13:17 | comment | added | Marco Ripà | @EmilJeřábek I implicitly assumed that taking $l_{upper}(k)$ as a proven upper bound for the given $k$-dimensional case of our problem would be clear by context. Basically, we have that $l_{upper}(k) \geq l_{min}(k)$ should hold for any $k$ and it must describe the total length of the tree that has been proven to be a valid tree for the given problem. | |
| Jun 11 at 13:16 | comment | added | David E Speyer | My guess is that the optimum is given by the tree with $2^k+2^{k-1} + \cdots + 2 = 2^{k+1}-2$ vertices, labeled by strings of the form $x_1 x_2 \cdots x_j$ with $x_i \in \{ \pm 1 \}$ and $1 \leq j \leq k$. Here $(x_1, \ldots, x_k)$ is the corresponding vertex of the cube, there are edges from $(x_1, \ldots, x_j)$ to $(x_1, \ldots, x_j, 1)$ and $(x_1, \ldots, x_j, -1)$, as well as a central edge from $(1)$ to $(-1)$, and all the angles are $120^{\circ}$. I don't know how to efficiently compute the coordinates of these vertices. | |
| Jun 11 at 13:15 | comment | added | David E Speyer | An optimum Steiner tree always has all internal vertices $3$-valent and all angles equal to $120^{\circ}$ (even in higher dimensions). | |
| Jun 11 at 13:10 | history | edited | Marco Ripà | CC BY-SA 4.0 |
$l_{upper}(k) = 1 + \sqrt{3}$ --> $l_{upper}(2) = 1 + \sqrt{3}$ since here we are only referring to the solution of the planar case.
|
| Jun 11 at 12:42 | comment | added | Emil Jeřábek | I skimmed through the Bridges paper. It’s not clear to me whether he really claims the value $1+3\sqrt3\approx6{.}196$ for $k=3$ is optimal, or whether it’s just the best he could find. FWIW, this is what it looks like: i.sstatic.net/Lhaeb69d.png | |
| Jun 11 at 12:23 | comment | added | Najib Idrissi | @HenrikRüping Mathematica thinks that you can get a total length of $\sqrt{30}+1 \approx 6.477$ at best if you keep $S_1$ and $S_2$ on the central axis. It's not reaching the bound $6.196$ mentioned by OP though. | |
| Jun 11 at 12:15 | comment | added | Emil Jeřábek | What does “$l_{upper}$” refer to in the P.P.S.? It’s not defined in the question. | |
| Jun 11 at 12:09 | comment | added | HenrikRüping | Thanks. It actually gives a better condition, namely that all the unit vectors pointing outwards need to add up to zero. This seems to show that the picture above is not optimal and by moving $S_1$ and $S_2$ inward a little bit, we should get a smaller total length. | |
| Jun 11 at 12:01 | history | edited | HenrikRüping | CC BY-SA 4.0 |
fixed broken link
|
| Jun 11 at 12:00 | history | edited | Peter Taylor | CC BY-SA 4.0 |
Add the standard terminology, known values; simplify the explanation of the recursively constructed upper bound
|
| Jun 11 at 11:52 | comment | added | Peter Taylor | @HenrikRüping, what little I can read of the paper I linked above (the first page) seems to suggest that this is incorrect in 3D (and presumably higher dimensions). | |
| Jun 11 at 11:50 | comment | added | HenrikRüping | I believe that whenever $n$ edges meet in one vertex in the optimal solution, they have to meet like the edges to the center of a regular tetrahedron. For example when 3 edges meet they should all have 120° angles between them. | |
| Jun 11 at 11:46 | comment | added | Emil Jeřábek | The problem is that, both in the title and in the text, when you write “join the vertices of the hypercube using a tree”, it strongly suggests that the vertices of the tree are vertices of the hypercube; moreover, this is the most natural thing that anyone familiar with graph theory would expect you to do. So unless one reads very carefully the rest of the text, it is prone to misunderstanding. | |
| Jun 11 at 11:36 | comment | added | Marco Ripà | @EmilJeřábek Picture edited. Please, let me know if the problem is clearly stated or if you wish the first lines of the post to meet a different definition with regards to the one considered in this article (that I also cited in previous papers of mine): semanticscholar.org/paper/… | |
| Jun 11 at 11:31 | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
there is no group operation here
|
| Jun 11 at 11:28 | history | edited | Marco Ripà | CC BY-SA 4.0 |
Fixing the typo k-->3
|
| Jun 11 at 11:25 | comment | added | Emil Jeřábek | @ManfredWeis The problem is not the picture, but the misleading terminology. The vertices of the trees are not supposed to be the vertices of the hypercube; you can add new vertices. So the question is not about spanning trees in the hypercube graph. | |
| Jun 11 at 11:18 | history | edited | Marco Ripà | CC BY-SA 4.0 |
Edited according to the suggestions in the comments and changed the original Figure in order to avoiding confusion about the tree/forest definitions
|
| Jun 11 at 11:13 | comment | added | Manfred Weis | @MarcoRipà can you please fix the picture in your question; it is no connected spanning tree and can you also clearly define whether the tree edges connect corners of the hypercube or if there may also be other vertices? | |
| Jun 11 at 10:44 | comment | added | Marco Ripà | @NoamD.Elkies I originally considered the tree $\{\{(0,0,0)-(1,1,0)\}\cup\{(1,0,0)-(0,1,0)\}\cup\{(\frac{1}{2},\frac{1}{2},0)-(\frac{1}{2},\frac{1}{2},1)\}\cup\{(0,0,1)-(1,1,1)\}\cup\{(1,0,1)-(0,1,1)\}$ with the two Steiner points $(\frac{1}{2},\frac{1}{2}, 0)$ and $(\frac{1}{2},\frac{1}{2},1)$, but I finally changed the picture as the above. Anyway, we agree that $2^k-1$ cannot be a solution for $k=3$ even by considering the tree whose branches meet in $(\frac{1}{2},\frac{1}{2},\frac{1}{2})$ and that joins every vertex of the unit cube from the center. | |
| Jun 11 at 9:51 | comment | added | Peter Taylor | For $k=3$, the optimum value is apparently approximately 6.196, per Bridges, Minimal Steiner Trees for Three Dimensional Networks, Mathematical Gazette Vol. 78, No. 482 (Jul., 1994), pp. 157-162. I don't have access to the paper itself and am relying on other sources which reference it. | |
| Jun 11 at 6:26 | comment | added | Gerry Myerson | @Steven, you may be right, in which case I'd say OP has no business making up new meanings for standard terms. | |
| Jun 11 at 4:30 | comment | added | Noam D. Elkies | For starters you can improve on that tree by replacing each X by a Steiner tree for the four vertices of a square. | |
| Jun 11 at 4:25 | comment | added | Steven Landsburg | @GerryMyerson : My understanding is that the OP defines a tree to be a collection of line segments that is connected as a topological space, regardless of whether it is connected as a graph (and also presumably regardless of whether it is simply connected). | |
| Jun 11 at 3:26 | comment | added | Saúl RM | Also see this question for the case $k=2$ (seems like this is called the Steiner tree problem) | |
| Jun 11 at 3:15 | comment | added | Saúl RM | It seems $l_{min}(3)<4\sqrt{2}+1$. E.g. consider a tree formed by joining the vertices of $\{0,1\}^3$ with $x_3=1$ to $(0.5,0.5,0.9)$, the ones with $x_3=0$ to $(0.5,0.5,0.1)$ and add the segment from $(0.5,0.5,0.1)$ to $(0.5,0.5,0.9)$ | |
| Jun 11 at 3:15 | comment | added | Gerry Myerson | The picture above is not a tree, but a forest, since it isn't connected. | |
| Jun 11 at 3:01 | history | edited | Marco Ripà | CC BY-SA 4.0 |
Fixing a typo and adding a P.S.
|
| Jun 11 at 2:52 | history | asked | Marco Ripà | CC BY-SA 4.0 |
