# From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives
## 3 Tree-Realizations of Barcodes
### Realizing Barcodes as Trees  
A geometric tree \(T\) is a _tree-realization_ of a barcode \(B\) if \(\text{TMD}(T)=B\), i.e., \(T\in\text{TMD}^{-1}(B)\). Examples of tree-realizations are provided in Figure 4B, while Figure 5 shows all the possible combinatorial types of tree-realizations of a strict barcode with \(n=4\).  
In Figures 4 and 5, we encode the combinatorial structure of the tree, i.e., how the branches may be attached to each other, in an adjacency matrix in which the \((i,j)\) coefficient is non-zero if the Elder Rule allows bar \(i\) to be connected to bar \(j\). For example, in Figure 4A, bars 1-3 may all be connected to the black bar 0, thus the coefficients \((0,1),(0,2),(0,3)\) are all non-zero in the corresponding adjacency matrix. Note that in each realization only a subset of these possible attachments is actually made (Figure 4B), since each branch can be attached to only one other branch.  
The connectivity diagram (bottom of Figure 4A) provides another representation of the pairs of branches that may be connected, in agreement with the Elder Rule. The arrow on an edge in the diagram indicates the direction of the connection. In this example, there are arrows from 0 towards 1, 2, and 3, from 1 to 2 and 3, and from 2 to 3.  
Figure 4: A strict barcode, whose bars are ordered according to birth times (greyscale), defines a unique ordering of death times. This ordering and the Elder Rule constrain the possible combinatorial types of trees that can be realized from this barcode. (**A**) the notation that will be used in this paper from a barcode that corresponds to an adjacency matrix of possible connectivities. Equivalently, the possible connectivities are presented in the connectivity diagram; (**B**) examples of possible tree realizations from branches that connect to the longest one (top) to random (bottom).  
For any strict barcode \(B\), let \(\mathcal{T}(B)\) denote the set of combinatorial equivalence classes of tree-realizations of \(B\), i.e.,  
\[\mathcal{T}(B)=\mathrm{TMD}^{-1}(B)/\underset{\mathrm{comb}}{\sim}.\]  
We can characterize the equivalence relation on strict barcodes in terms of \(\mathcal{T}(B)\).  
Lemma 1: _If \(B\) and \(B^{\prime}\) are two strict barcodes with the same number of bars, then_  
\[B\underset{\mathrm{bar}}{\sim}B^{\prime}\iff\mathcal{T}(B)=\mathcal{T}(B^{ \prime}).\]  
Proof: The order of the deaths in a strict barcode \(B\) completely determines the set of combinatorial equivalence classes of its possible tree realizations.  
Indeed, the two pairs of bars in Figure 6B lead to the same adjacency possibilities for their respective branches. Only move (A) in Figure 6, corresponding to switching the order of the deaths of the two bars, modifies the permutation equivalence class of the barcode, hence also the set of trees that return the given barcode.  
Figure 5: Tree-realizations of all possible strict barcodes \(B\) with four bars. Each row (left) represents a possible permutation of death times for the corresponding order of bars in \(B\), i.e., a possible TMD-type. Each barcode can be realized by a subset of all the combinatorial tree types, each represented by a column, with a corresponding adjacency matrix.