What is Merge Tree?

A merge tree is a pair \((T, f)\) of a finite rooted tree \(T\) with vertex set \(V(T)\) and a function $$ f : V (T) \rightarrow \mathbb{R} \cup {\infty} $$ such that adjacent vertices do not have equal function value, every non-root vertex has exactly one neighbour with higher function value, and the root (a degree one node) is the only point with the value \(\infty\).

A labeled merge tree is a merge tree with a map \(\pi: [n] \rightarrow V(T)\), which is subjective on the leaves.

A merge tree

Useful properties of labeled merge trees:

  • The space of merge trees (\(MT\)) can be viewed as a metric space with a choice of metric, such as the interleaving distance.
  • Merge tree structure induces a poset relation on the vertices of \(T\).
  • There is a natural way to associate a matrix to a labeled merge tree through the lowest common ancestor (LCA) as follows:

$$ \mathcal{M}(T,f,\pi)_{ij} = f(\text{LCA}(\pi (i), \pi (j))) $$ - The induced matrix is an ultra matrix.

Note: A symmetric matrix \(M \in \mathbb{R}^{n \times n}\) is an ultra matrix if \(M_{ii} \leq M_{ij}\) for all \(1 \leq i,j \leq n\) and \(M_{i,j} \leq \max\{M_{i,k},M_{k,j} \}\) for every \(1 \leq k \leq n\).

  • \(\mathcal{M}\) induces a bijection between labeled merge trees and ultra matrices.