Merge trees in discrete Morse theory (Q2168877): Difference between revisions

A merge tree is a full binary tree, that is, a binary tree with at most one vertex of degree two. Merge trees are considered to have a root, and a planar embedding so that two trees which are isomorphic as graphs, can be two different merge trees if they are embedded in the plane differently. A merge tree is called thin, if the amount of vertices which are adjacent to two leaves, is one. Given a discrete Morse function \(f\) on a tree \(T\), the authors show that \(f\) induces a well-defined merge tree \(M_f\). Moreover, two discrete Morse functions \(f,g :T \rightarrow \mathbb{R}\) are merge equivalent if they induce the same merge tree. Two discrete Morse functions are Forman equivalent if they induce the same gradient vector field, and they are persistent equivalent if they induce the same persistence diagram. Given a graph with a discrete Morse function, one may study the Betti numbers of the level subcomplexes induced by the critical values. This gives rise to the homological sequence, and two Morse functions are homologically equivalent if they induce the same homological sequence. The authors give examples of discrete Morse functions which are Forman equivalent or persistent equivalent but not merge equivalent, and show that homological equivalence and merge equivalence do not imply each other. The authors focus on the special case when \(T\) is a star \(S_n = K_{1, n-1}\), and have the following results. \textbf{Proposition} If \(T= S_n\) is a star graph, and \(f : S_n \rightarrow \mathbb{R}\) is any discrete Morse function, then \(M_f\) is a thin merge tree. \textbf{Theorem} Suppose \(M\) is a thin merge tree. Then there is a star graph \(S_n\) and a discrete Morse function \(f: S_n \rightarrow \mathbb{R}\) such that \(M= M_f\). Finally the authors conclude with the open questions: Can one characterize the set of all merge equivalent discrete Morse functions on a caterpillar graph, regular tree, binary tree, or other class of trees? Can any merge tree be realized by a discrete Morse function on some graph? The authors conjecture that this can be done with the right discrete Morse function on a path. Conversely they also conjecture that if \(T\) is a tree which is not a path, then there exists a merge tree that cannot be realized by any discrete Morse function on \(T\).