Unique Partition of $\{1, \dotsc, n\}$ by Ultrametric Property

Question

I'm currently working on a proof which states (not the main claim, just a property used later on in the proof):

Let $d=(d_{ij})$ be an ultrametric on the set $\{1, \dotsc, n\}$ (i.e. that $d$ is a vector in $\mathbb{R}^{\binom{n}{2}}$ and its coordinates are considered as an ultrametric such that $d(i,j)=d_{ij}$). Set $R= \max \{d_{ij} \}$.

CLAIM: Then there exists a unique partition of the set $\{1, \dotsc, n \}$ such that $d_{ij}=R$ if $i$ and $j$ are from different blocks and such that $d_{ij}<R$ if $i,j$ are in the same block.

According to the proof, this follows immediately from the ultrametric property, i.e from the fact that since $d$ is an ultrametric, $\max \{d_{ij},d_{ik}, d_{jk} \}$ is attained at least twice. However, I fail to see how I could show this. I thought that certainly $R$ is attained several times due to the ultrametric property...It would be great if someone could point me in the right direction on how to approach this.

Answer 1

Partitions and equivalence relations are the same thing, so all we need to show is that, if $i\sim j$ means $d_{ij} < R$, then $\sim$ is an equivalence relation.

Reflexivity and symmetry follow from straightforward properties of a metric. To see transitivity, we need the ultrametric property:

If $d_{ij} < R$ and $d_{jk} < R$, then $d_{ik} \leq \max(d_{ij}, d_{jk}) < R$. And that's it!

Note that we didn't use any properties of $R$ except that it's a positive real number. Choosing $R$ to be the maximum distance gives us other interesting properties, e.g. that the resulting partition is nontrivial.

Answer 2

The crux of this is the following fact. Given $i$ let $A = \{ j : d(i,j) < R \}$. Then

1. $d(j,k) < R$ for all $j,k \in A$, and
2. $d(j,\ell) \geq R$ for all $j \in A$ and all $\ell \notin A$.

Suppose that $j,k \in A$ are given. By the ultrametric property we know that $d(j,k) \leq \max \{ d(i,j) , d(i,k) \}$, and since $j,k \in A$ by definition $d(i,j) , d(i,k) < R$, so then $d (j,k) < R$.

Suppose that $j \in A$ and $\ell \notin A$ are such that $d(j,\ell) < R$. By the ultrametric property we have that $d(i,\ell) \leq \max \{ d(j,i) , d (j,\ell) \}$. By definition of $A$ we have that $d(j,i) < R$ and by assumption $d ( j,\ell ) < R$, so that it must be that $d(i,\ell) < R$. But this contradicts that $\ell \notin A$!

---

With this in hand, we simply build up the blocks recursively. Set $i_1 = 1$, and let $A_1 = \{ j : d ( i_1, j ) < R \}$. If there are no points left, we're done. Otherwise let $i_2$ be the least number not in $A_1$, and let $A_2 = \{ j : d ( i_2 , j ) < R \}$. If all points are in $A_1 \cup A_2$, we're done. Otherwise let $i_3$ be the least number not in $A_1 \cup A_2$, and let $A_3 = \{ j : d ( i_3 , j ) < R \}$. &c.

Sooner or later this process will stop with sets $A_1 , A_2 , \ldots , A_m$. Our fact above can be used to show that these sets are disjoint, and have the desired "ultrametric" properties.