Vector Embedding of Subtrees

From a Subtree to a Vector, and Back Again

1. The Phenomenon

Let $T=(V,E)$ be a tree whose edges have positive lengths $\ell_e$, and let $M(T)$ denote its metric realization. For a subtree $X\subseteq M(T)$, define its edge-length representation by

$$\Phi(X)=x\in\mathbb R^E,$$

where

$$x_e=\operatorname{len}(X\cap e),\qquad e\in E.$$

Thus every pair $(X,T)$ naturally produces a pair $(x,E)$ through

$$(X,T)\xrightarrow{\Phi}(x,E).$$

The vector $x$ records how much of the subtree lies on each edge, while the edge set $E$ becomes the index set of the vector. This representation separates two kinds of information. The numerical values $x_e$ retain the amount of the subtree contained in each edge, whereas the geometric relations among these pieces originate from the tree structure of $T$.

2. The Reconstruction Question

The natural inverse question is whether this representation can be reversed:

$$(x,E)\longrightarrow(X,T)\ ?$$

More precisely, given a set $E$ and a vector

$$x=(x_e)_{e\in E}\in\mathbb R^E,$$

when can one explicitly construct a tree $T$ with edge set $E$ and a subtree $X\subseteq M(T)$ such that

$$\Phi(X)=x?$$

This problem is not trivial because the vector $x$ alone does not contain the connectivity information carried by the original tree.

For example, consider a path consisting of three consecutive edges $e_1,e_2,e_3$, each of unit length. The vector

$$x=\left(\frac12,0,\frac12\right)$$

cannot represent a subtree. Indeed, if a subtree intersects both $e_1$ and $e_3$, then it must contain the unique path connecting these two parts. Consequently, it must also intersect the intermediate edge $e_2$, contradicting $x_{e_2}=0$.

This example reveals the essential obstruction. The coordinates of $x$ cannot be treated independently. A subtree is connected through the unique paths of the ambient tree, and this connectivity imposes relations among the edge coordinates. Hence reconstructing $X$ requires not only the values $x_e$, but also sufficient structure on the index set $E$ to recover how the corresponding edges are connected.

3. A Possible Route: Tree Extension of the Edge Set

The proposed idea is to restore the missing tree structure directly on the index set $E$.

Introduce one formal element $e_0$ and define

$$\widehat E=E\sqcup\{e_0\}.$$

Equip $\widehat E$ with a parent map

$$p:\widehat E\to\widehat E,\qquad p(e_0)=e_0,$$

such that the relations

$$e\longrightarrow p(e),\qquad e\in E,$$

form a rooted tree with sink $e_0$. We refer to the resulting structure $(\widehat E,p,e_0)$ as a tree extension of $E$.

Once such a tree extension is available, the vector $x$ should satisfy a filling property. Namely,

$$x_e>0,\quad p(e)\neq e_0\quad\Longrightarrow\quad x_{p(e)}=\ell_{p(e)}.$$

Geometrically, if the reconstructed subtree occupies a positive portion of an edge, then the preceding edge toward the root must already be completely filled. Repeated application of this local condition forces all preceding edges on the route toward the root to be filled. Thus a global connectivity requirement is encoded by a local parent relation.

This leads to a constructive route:

$$(x,E)\longrightarrow(\widehat E,p,e_0)\longrightarrow T\longrightarrow X.$$

The tree extension first reconstructs the combinatorial organization of the edges. The vector $x$ then determines how much of each edge belongs to $X$, while the parent structure determines from which side of each edge that portion is taken. The filling property guarantees that these edge portions join consistently into a subtree.

The main insight is that the inverse problem separates naturally into a structural component and a numerical component:

$$\text{edge values }x+\text{tree structure on }E\quad\Longrightarrow\quad\text{subtree geometry}.$$

Thus the information apparently lost under $\Phi$ is not primarily numerical. What is missing from $x\in\mathbb R^E$ is the tree structure carried by its index set. A tree extension provides a minimal way to restore this structure and opens a direct route toward an explicit reconstruction theorem.