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

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} 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.

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.

• Thank you for your answer. However, I was wondering if it is really applicable to my context. In the proof, they then proceed to calculate some values for different blocks/partitions - so they actually consider elements within these blocks. So I wanted to ask if I can still use your argument or need to argue as suggested in the other answer (which actually defines these blocks)? – SallyOwens Nov 14 '18 at 11:08
• @SallyOwens I defined the blocks—they're the equivalence classes. All the other answer does is order them, which we can do as follows: Set $i_1=1$, let $A_1$ be the equivalence class of $i_1$. Let $i_2$ be the smallest number not in $A_1$, and let $A_2$ be the equivalence class of $i_2$... – Slade Nov 14 '18 at 11:22
• Ah, of course - thank you! – SallyOwens Nov 14 '18 at 13:42

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.