ultrametric

Any metric $d:X\times X\to\mathbb{R}$ on a set $X$ must satisfy the triangle inequality:

 $(\forall x,y,z)\quad d(x,z)\leq d(x,y)+d(y,z)$

An ultrametric must additionally satisfy a stronger version of the triangle inequality:

 $(\forall x,y,z)\quad d(x,z)\leq\max\{d(x,y),d(y,z)\}$

Here is an example of an ultrametric on a space with 5 points, labelled $a,b,c,d,e$:

 $\begin{array}[]{c|c|c|c|c|c}&a&b&c&d&e\\ \hline a&0&12&4&6&12\\ \hline b&&0&12&12&5\\ \hline c&&&0&6&12\\ \hline d&&&&0&12\\ \hline e&&&&&0\end{array}$

In the table above, an entry $n$ in the for element $x$ and the for element $y$ indicates that $d(x,y)=n$, where $d$ is the ultrametric. By symmetry of the ultrametric ($d(x,y)=d(y,x)$), the above table yields all values of $d(x,y)$ for all $x,y\in\{a,b,c,d,e\}$.

The ultrametric condition is equivalent to the ultrametric three point condition:

 $(\forall x,y,z)\quad x,y,z\textrm{ can be renamed such that }d(x,z)\leq d(x,y)% =d(y,z)$

Ultrametrics can be used to model bifurcating hierarchical systems.  The distance between nodes in a weight-balanced binary tree is an ultrametric. Similarly, an ultrametric can be modelled by a weight-balanced binary tree, although the choice of tree is not necessarily unique.  Tree models of ultrametrics are sometimes called ultrametric trees.

The metrics induced by non-Archimedean valuations are ultrametrics.

Title ultrametric Ultrametric 2013-03-22 13:28:28 2013-03-22 13:28:28 Koro (127) Koro (127) 21 Koro (127) Definition msc 54E35 MetricSpace Valuation UltrametricSpace