# From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives
## 3 Tree-Realizations of Barcodes
### The Combinatorics of Tree-Realization
In a tree-realization of \(B^{\prime}\), the branch corresponding to the red bar can be attached to any of the branches corresponding to the 0 th, 1 st, and 2 nd bars, represented on the trees by the red branches. This leads to nine possible combinatorial equivalence classes of trees for the barcode (2134). Figure 7: A representation of the space of barcodes with four bars up to permutation equivalence class as the Cayley graph of \(\mathfrak{S}_{3}\) generated by the transpositions (12) and (23), respectively. Each vertex is an element of the group. The edges represent the transposition to convert one end point into the other, colored by generator. The number to the right of each bar is its index. All trees \(T\) such that \(\mathrm{TMD}(T)=B\) are indicated next to a barcode \(B\) with the corresponding tree type of Figure 5. The number of such trees can be computed using Lemma 2. **Proposition 1**. : _Let \(B=\{(b_{i},d_{i})\}_{i=0,\ldots n}\) be a strict barcode in the equivalence class (\(i_{1}\)...\(i_{n}\)). Let \(B^{\prime}=\{(b^{\prime}_{i},d^{\prime}_{i})\}_{i=0,\ldots n}\) be a new barcode obtained by permuting the deaths \(d_{i_{k}}\) and \(d_{i_{k+1}}\), i.e., \(b_{i}=b^{\prime}_{i}\) for all \(i\) and \(d_{i}=d^{\prime}_{i}\) for all \(i\
eq i_{k}\), \(i_{k+1}\), while \(d_{i_{k}}=d^{\prime}_{i_{k+1}}\) and \(d_{i_{k+1}}=d^{\prime}_{i_{k}}\)._  
1. _If_ \(i_{k}<i_{k+1}\)_, then_ \(\operatorname{index}_{i_{k+1}}(B^{\prime})=\operatorname{index}_{i_{k+1}}(B)-1\)_, and_ \[\operatorname{index}_{i}(B)=\#\{j\mid b_{j}<b_{i}<d_{i}<d_{j}\}=\#\{j<i\mid d_ {i}<d_{j}\}.\]0
2. _If_ \(i_{k}>i_{k+1}\)_, then_ \(\operatorname{index}_{i_{k+1}}(B^{\prime})=\operatorname{index}_{i_{k+1}}(B)+1\)_, and_ \[\operatorname{index}_{i}(B)=\#\{j\mid b_{j}<b_{i}<d_{i}<d_{j}\}=\#\{j<i\mid d_ {i}<d_{j}\}.\]1  
Proof. : It is enough to prove (1), since (2) then follows by switching the roles of \(B\) and \(B^{\prime}\). If \(i_{k}<i_{k+1}\), then \(b_{i_{k}}<b_{i_{k+1}}\). Since \(B\) is in the equivalence class (\(i_{1}\)...\(i_{n}\)), \(d_{i_{k+1}}<d_{i_{k}}\) as well, whence \((b_{i_{k+1}},d_{i_{k+1}})\subset(b_{i_{k}},d_{i_{k}})\). On the other hand, \((b^{\prime}_{i_{k+1}},d^{\prime}_{i_{k+1}})\
otin(b^{\prime}_{i_{k}},d^{\prime }_{i_{k}})\), but otherwise respects all of the same inclusion relations as \((b_{i_{k+1}},d_{i_{k+1}})\), so that  
\[\operatorname{index}_{i}(B)=\#\{j\mid b_{j}<b_{i}<d_{i}<d_{j}\}=\#\{j<i\mid d_ {i}<d_{j}\}.\]2  
as desired. Moreover, \((b^{\prime}_{i_{k}},d^{\prime}_{i_{k}})\
otin(b^{\prime}_{i_{k+1}},d^{\prime }_{i_{k+1}})\), so \((b^{\prime}_{i_{k}},d^{\prime}_{i_{k}})\) respects exactly the same inclusion relations as \((b_{i_{k}},d_{i_{k}})\), i.e.,  
\[\operatorname{index}_{i}(B)=\#\{j\mid b_{j}<b_{i}<d_{i}<d_{j}\}=\#\{j<i\mid d_ {i}<d_{j}\}.\]3  
Because no other bars are affected when passing from \(B\) to \(B^{\prime}\), we can conclude. **Example 2**. : _In Figure 9, we show all the possible death-transpositions in a strict barcode with five bars. As an example, take \(B\) in the equivalence class (2134), so the barcode satisfies \(d_{2}>d_{1}>d_{3}>d_{4}\). The index of \((b_{4},d_{4})\) is 4 because it is included in all the other bars. Permuting \(d_{3}\) and \(d_{4}\) leads to a barcode in the equivalence class (2143). The index of the last bar is now \(3\) because it is no longer included in the third bar._  
\[\operatorname{index}_{i}(B)=\#\{j\mid b_{j}<b_{i}<d_{i}<d_{j}\}=\#\{j<i\mid d_ {i}<d_{j}\}.\]4 The Cayley graph representing \(\mathfrak{S}_{4}\) generated by (12), (23), (34). For the four outside elements, we provide the barcode associated with the permutation. The number next to each bar is its index. Recall the bijection \(\sigma:B_{n}^{\text{st}}\to\mathfrak{S}_{n}\) from Section 2.2. Permuting the order of the deaths \(d_{i}\) and \(d_{i+1}\) corresponds to a transposition \((i,i+1)\) in \(\mathfrak{S}_{n}\) (and to move (A) in Figure 6).