5
$\begingroup$

Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the maximal volume of the convex hull of an embedding into $\mathbb R^3$ of any such "labelled" $T$. It is clear that two homeomorphic trees (i.e. which can be obtained from each other by adding and/or deleting vertices of degree 2) have the same $v(T)$. Moreover, extremal labelled trees of $\mathcal T_n$ may be "degenerated" in the sense that some edges may have length $0$, and so should be rather considered as belonging to some unique $\mathcal T_k$ with $k<n$.

For example, for a path $P_4=ABCD$ of three edges, we have $v(P_4)=\dfrac1{162}\approx 0.00617$, as it is easy to see that for a tetrahedron of maximal volume spanned by it, the three edges $AB,BC,CD$ must be of equal length and pairwise orthogonal.
If $T$ is a claw, we get again easily $v(K_{3,1})=\dfrac1{162}$, realized this time by a claw-spanned tetrahedron $OABC$ with orthogonal sides $OA=OB=OC=\dfrac13$.

This raises the following question:

For given $n$, which kinds of trees $T\in\mathcal T_n$ (excluding degenerate ones) maximize or minimize $v(T)$?

I'd conjecture that for $n\ge5$ all minimizing trees are homeomorphic to $K_{4,1}$ with $v(K_{4,1})=\dfrac{\sqrt{3}}{216}\approx 0.00802$ (volume of a regular tetrahedron spanned by its four circumradii of length $\dfrac14$), unless there are some Steiner-like trees that do worse (but still produce local maxima).

As for the maximizing tree, is it always the path $P_n$? Note that for growing $n$, the optimal path embeddings, if done in similar ways, will necessarily converge towards the(?) optimal curve of length $1$ in $\mathbb R^3$ - but the problem of finding that optimal curve is still open, though conjecturally it is a certain helix, which spans a volume $\sim.0102$.

$\endgroup$
3
  • 1
    $\begingroup$ Are edges straight line segments? $\endgroup$ Nov 16, 2015 at 21:21
  • $\begingroup$ @PietroMajer Yes, otherwise all paths would reduce to $P_2=K_2$, and for a tree that is not a path, well, non-straight lines would need to be on the boundary - and that would be a different problem even harder than the $P_2$ (simple curve) case. $\endgroup$
    – Wolfgang
    Nov 17, 2015 at 7:36
  • $\begingroup$ Maybe the calculus-of-variations tag is misleading here. $\endgroup$
    – Wolfgang
    Nov 17, 2015 at 7:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.