The Tropical Algebra of Binary-Tree Height

Abstract

The binary-tree height recursion defines an algebra $\mathcal{H}$ on $\mathbb{N}\cup \{-\infty \}$, with join given by $\max$ and product \[ a\star b=\max\{a,b\}+1. \] We show that weighted evaluation of a labelled tree depends only on the greatest depth of each label. Single-tree profiles are exactly the vectors satisfying the binary Kraft inequality, while finite joins realize every vector in $(\mathbb{N}\cup \{-\infty \}{)}^n$; hence the $n$-variable term operations form the free algebra ${\mathcal{H}}^n$. We also classify $\mathcal{H}$'s compatible semilattice operation, subalgebras, endomorphisms, congruences, and finite quotients, and recover the dyadic-composition spectrum at the full-linear boundary.

26 pages