# Formal Definition of Tree-Consistent

I am working my way through this paper on Bayesian Hierarchical Clustering. I keep seeing the phrase tree-consistent. However, it doesn't seem to be defined anywhere in the paper. There is a description of the concept in figure 1.b, but it isn't a formal definition really. I have looked in other papers on the topic referencing the idea of tree-consistency and noticed that they don't formally define the concept either. Although I may be overlooking a paper on the topic.

Does anyone know of a formal definition for this?

Thanks

IMHO, with the passage and figure below Heller and Ghahramani provide the definition of tree-consistent to warrant the use of the concept in the paper.

At each stage the algorithm considers merging all pairs of existing trees. For example, if Ti and Tj are merged into some new tree Tk then the associated set of data is Dk = Di∪Dj (see figure 1(a)).

Furthermore, on page 2 they say "([w]e elaborate on the notion of tree-consistent partitions in section 3 and figure 1(b))." Indeed, the passage below from section 3 provides further insights into the notion of tree-consistent:

Proposition 1 The number of tree-consistent partitions is exponential in the number of data points for balanced binary trees.

Proof If Ti has Ci tree-consistent partitions of Di and Tj has Cj tree-consistent partitions of Dj , then Tk = (Ti, Tj ) merging the two has CiCj + 1 tree-consistent partitions of Dk = Di ∪ Dj , obtained by combining all partitions and adding the partition where all data in Dk are in one cluster. At the leaves Ci = 1. (...)