From trees to barcodes and back again. II: Combinatorial and probabilistic aspects of a topological inverse problem (Q6049548)

Persistent homology [\textit{H. Edelsbrunner} and \textit{J. Harer}, Contemp. Math. 453, 257--282 (2008; Zbl 1145.55007)] produces successful shape summaries (``barcodes'' or ``persistence diagrams'') because it forgets in a smart way. But what does it forget? Moreover, given a barcode, is there always an object to which it corresponds? Otherwise said, seeing a barcode as the result of a functor, what is its pre-image? This speculation, as reported in the present paper, started when dealing with universality [\textit{M. Lesnick}, Found. Comput. Math. 15, No. 3, 613--650 (2015; Zbl 1335.55006)], and even before in the framework of ``size functions'' [\textit{M. d'Amico} et al., Acta Appl. Math. 109, No. 2, 527--554 (2010; Zbl 1198.68224)]. The study of such pre-images is the central goal of this paper. Although barcodes can be defined for filtered topological spaces or simplicial complexes of any dimension, the essence of the problem can be captured by restricting the domain to trees. In the background chapter and the appendix, different types of trees are defined and compared. The typical object dealt with in this paper is a \textit{merge} tree \((T, h)\): It has a distinguished vertex \(r\) (called \textit{root}), has vertices of degree three (called \textit{deaths}) and of degree one (called \textit{terminations}; these are the root and the \textit{births}), and a height function, that I now define. A vertex \(v\) is the \textit{parent} of a vertex \(w\) if \(v\) is the last vertex met in the unique path from the root to \(w\), before \(w\) itself. A \textit{height} function is a labeling \(h:V(T) \to \mathbb{R}\cup \{\infty\}\) such that 1) if \(v\) is parent of \(w\), then \(h(v)\ge h(w)\), and 2) \(h(r)=\infty\). Two merge trees \((T, h)\), \((T', h')\) are \textit{combinatorially equivalent} if there exists an isomorphism between \(T\) and \(T'\) that respects the order induced by the labeling on the births and the one induced on the deaths. I refer to the quoted survey or to [\textit{H. Edelsbrunner} and \textit{J. L. Harer}, Computational topology. An introduction. Providence, RI: American Mathematical Society (AMS) (2010; Zbl 1193.55001)] for the construction of the barcode of a merge tree. Such a barcode is formed by a right half-line starting at the least vertex height and by some intervals \([b_j, d_j)\) (\textit{bars}), where \(b_j\) is the height of a birth and \(d_j\) is the height of a death. The \textit{realization number} of a barcode \(B\) is the number of merge trees giving rise to \(B\). A first remarkable result is Proposition 2.18, which provides the realization number in terms of indices, easily computed from the bars of \(B\). Consider as fundamental permutations of births and of deaths the ones corresponding to increasing heights. Then, if the \(b_j\)'s are in fundamental permutation, the corresponding \(d_j\)'s will form a certain permutation \(\sigma\). Lemma 2.25 asserts that the barcodes of combinatorially equivalent merge trees give rise to the same permutation. The \textit{left inversion vector} of a permutation \(\sigma\) keeps track of the inversions in \(\sigma\). Lemma 3.4 expresses the realization number of \(B\) as the product of the elements of the left inversion vector of the associated \(\sigma\). One can then speak of the realization number of \(\sigma\) itself; this is shown to be monotonically increasing with the left Bruhat order of permutations (Lemma 3.13). The paper also analyzes the set of barcodes giving rise to a given \(\sigma\); Lemma 3.6 asserts that this set is convex, with respect to intuitive sum and multiplication by a scalar of barcodes. The paper contains other formulas concerning the sum of the realization numbers of permutations across the symmetric group on \(n\) elements. A final section is dedicated to the probabilistic study of the expected tree realization number.