Notes 42 · Full lecture · 75 minutes
CS 574 · University of Illinois, Urbana-Champaign · Fall 2026
Random partitions preserve small neighborhoods with useful probability. The FRT partition lemma is the main tool of this lecture.
| Topic | Minutes |
|---|---|
| Metrics, distortion, and motivation | 10 |
| Partition construction and FRT lemma | 35 |
| Random trees and \(k\)-median | 10 |
| Euclidean embeddings | 17 |
| Recap and exercises | 3 |
\(X\) is a set of \(n\) points; \(d:X\times X\to[0,\infty)\) satisfies
\[ d(x,y)=0\iff x=y,\qquad d(x,y)=d(y,x), \] \[ \boxed{d(x,z)\leq d(x,y)+d(y,z).} \]
The triangle inequality will control both cluster diameters and cut probabilities.
A finite metric can be specified by \(\binom n2\) pairwise distances: a complete weighted graph satisfying the triangle inequality.
A connected undirected graph with positive edge lengths gives the metric \[d_G(x,y)=\text{length of a shortest path from }x\text{ to }y.\] A sparse graph can represent its metric compactly.
We use open balls, as in the notes: \[B(x,r)=\{y\in X:d(x,y)<r\}.\] For a nonempty set \(C\subseteq X\), \[\operatorname{diam}(C)=\max_{u,v\in C}d(u,v).\]
A ball radius and a cluster diameter are different parameters. Two points in a radius-\(R\) ball can be almost \(2R\) apart.
For \(f:(X,d_X)\to(Y,d_Y)\), \(C\)-Lipschitz means \[d_Y(f(x),f(y))\leq C\,d_X(x,y).\] \(K\)-bi-Lipschitz means that some \(C>0\) satisfies \[\frac C K d_X(x,y)\leq d_Y(f(x),f(y))\leq C d_X(x,y).\]
The least such \(K\) is the distortion. A common scale factor is allowed.
In the unit-edge three-leaf star, \[d(s,a)=d(s,b)=d(s,c)=1,\qquad d(a,b)=d(b,c)=d(c,a)=2.\] The notes’ equilateral-triangle calculation gives \[\operatorname{distortion}(f)\geq \frac{2}{\sqrt3}>1.\]
The points are leaves of a rooted tree. Each node has a label \(\Delta_v\): \[\Delta_v=0\iff v\text{ is a leaf},\qquad \Delta_u\leq\Delta_v\quad(u\text{ child of }v).\] \[\boxed{d_T(x,y)=\Delta_{\operatorname{lca}(x,y)}.}\]
For a \(k\)-HST, \(\Delta_u\leq\Delta_v/k\) along every parent–child edge.
For the unit-edge cycle \(C_n\), a noncontracting HST embedding has \[\operatorname{distortion}(f)\geq\lfloor n/2\rfloor.\] Some adjacent cycle vertices separate at the top relevant tree split.
The notes instead seek a distribution of trees: \[d_T(x,y)\geq d(x,y),\qquad \mathbb E[d_T(x,y)]\leq O(\log n)\,d(x,y).\] The expectation is for each fixed pair.
Choose \(C\subseteq X\), \(|C|=k\), minimizing \[\operatorname{cost}_d(C)=\sum_{p\in X}d(p,C),\qquad d(p,C)=\min_{c\in C}d(p,c).\]
The notes give an \(O(k^2n)\) dynamic program on an HST. Embed into a random HST, solve there, and return its centers in \(X\).
\[P=\{C_1,\ldots,C_m\},\qquad X=\bigcup_{i=1}^m C_i,\qquad C_i\cap C_j=\varnothing\ (i\ne j).\] \(P(x)\) denotes the unique cluster containing \(x\).
We want small cluster diameters, while keeping a small ball \(B(x,t)\) inside \(P(x)\) with high probability.
Fix a diameter scale \(\Delta>0\) (the notes use dyadic scales).
There is one shared radius for this partition. The permutation decides which center claims a point first.
Write \(\pi=(z_1,\ldots,z_n)\). Then \[C_{z_i}=B(z_i,R)\setminus\bigcup_{h<i}B(z_h,R).\] Discard empty clusters.
Every point is assigned: \(x\in B(x,R)\). Assignments are unique: the first eligible center wins.
Only the part of a new ball not already claimed becomes a new cluster.
The radius remains fixed throughout this partition.
Clusters need not themselves be balls.
For \(u,v\in C_z\subseteq B(z,R)\), \[d(u,v)\leq d(u,z)+d(z,v)<2R\leq\Delta.\] Therefore \[\boxed{\operatorname{diam}(C_z)\leq\Delta.}\]
This conclusion holds for every permutation and every allowed radius.
Fix \(x\in X\) and \(0<t\leq\Delta/8\). Let \[a=|B(x,\Delta/8)|,\qquad b=|B(x,\Delta)|.\] Then \[\boxed{\Pr[B(x,t)\nsubseteq P(x)] \leq\frac{8t}{\Delta}\ln\frac ba.}\] Every cluster has diameter at most \(\Delta\).
\[\underbrace{\frac{8t}{\Delta}}_{\text{relative radius}} \quad\cdot\quad \underbrace{\ln\frac{|B(x,\Delta)|}{|B(x,\Delta/8)|}}_{\text{local growth}}.\]
Since \(1\leq a\leq b\leq n\), \[\Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t}{\Delta}\ln n.\] The sharper local ratio is what the tree analysis uses.
Keep \(x,t,\Delta\) and the input metric fixed. Write \[B=B(x,t).\] First condition on the value of \(R\); the permutation remains uniform.
We will use a fixed distance order for the proof. This order is different from the random permutation \(\pi\).
If \(B(w,R)\cap B\ne\varnothing\), choose \(z\) in the intersection: \[d(x,w)\leq d(x,z)+d(z,w)<t+R.\] Thus every center that can affect \(B\) belongs to \[A_R=\{w\in X:d(x,w)<R+t\}.\]
Some centers in \(A_R\) might not actually touch \(B\). That is harmless.
\[R+t\leq\frac\Delta2+\frac\Delta8=\frac{5\Delta}{8}<\Delta.\] Therefore \[A_R\subseteq W:=B(x,\Delta),\qquad |W|=b.\]
Order this fixed set by distance from \(x\): \[d(x,w_1)\leq d(x,w_2)\leq\cdots\leq d(x,w_b).\] Break equal-distance ties in any fixed way.
Let \(q\) be the first center of \(A_R\) in permutation order. If \(d(x,q)\leq R-t\), then for every \(z\in B\), \[d(q,z)\leq d(q,x)+d(x,z)<(R-t)+t=R.\]
No earlier center can touch \(B\). Hence \(B\subseteq C_q=P(x)\).
Taking the contrapositive: \[B\nsubseteq P(x)\quad\Longrightarrow\quad R-t<d(x,q)<R+t.\] Equivalently, if \(q=w_k\), \[R\in I_k:=[d(x,w_k)-t,\ d(x,w_k)+t].\]
The interval has length \(2t\). This is where the random radius helps.
These are triangle-inequality statements, valid in every metric. They do not assume Euclidean geometry or convexity.
\[R\sim\operatorname{Unif}[\Delta/4,\Delta/2],\qquad |[\Delta/4,\Delta/2]|=\Delta/4.\] For every fixed \(k\), \[\Pr[R\in I_k] =\frac{|I_k\cap[\Delta/4,\Delta/2]|}{\Delta/4} \leq\boxed{\frac{8t}{\Delta}}.\]
The intersection can only shorten the interval.
\[\frac{\text{length of possible bad radii}}{\text{length of sampling interval}} \leq\frac{2t}{\Delta/4}=\frac{8t}{\Delta}.\]
For \(k\leq a\), \(d(x,w_k)<\Delta/8\). Since \(t\leq\Delta/8\), \[d(x,w_k)+t<\Delta/4\leq R.\] Such a center’s radius-\(R\) ball contains all of \(B\).
The witness of a cut must have rank \(k>a\). This is why the final logarithm starts at \(a\), rather than at \(1\).
Suppose the first candidate \(q\) has distance rank \(k\). Then all of \(w_1,\ldots,w_k\) are in \(A_R\). Consequently \(w_k\) must appear first among these \(k\) points in \(\pi\).
Uniform permutation symmetry gives \[\boxed{\Pr[w_k\text{ is first among }w_1,\ldots,w_k]=\frac1k.}\]
Define the possible-witness event \[A_k=\{R\in I_k\}\cap \{w_k\text{ first among }w_1,\ldots,w_k\text{ in }\pi\}.\] The distance order and \(I_k\) are fixed, while \(R\) and \(\pi\) are independent: \[\Pr[A_k]\leq\frac{8t}{\Delta}\cdot\frac1k.\]
If \(B\) is cut, its first candidate has some rank \(k>a\) and satisfies \(A_k\). Therefore \[\{B\nsubseteq P(x)\}\subseteq\bigcup_{k=a+1}^{b}A_k.\]
By the union bound, \[\Pr[B\nsubseteq P(x)] \leq\frac{8t}{\Delta}\sum_{k=a+1}^{b}\frac1k.\]
For \(k\geq a+1\), \[\frac1k\leq\int_{k-1}^{k}\frac{du}{u}.\] Summing, \[\sum_{k=a+1}^{b}\frac1k \leq\int_a^b\frac{du}{u}=\ln b-\ln a=\boxed{\ln\frac ba}.\]
\[ \begin{aligned} \Pr[B(x,t)\nsubseteq P(x)] &\leq\sum_{k=a+1}^{b}\Pr[A_k]\\ &\leq\sum_{k=a+1}^{b}\frac{8t}{\Delta k}\\ &\leq\frac{8t}{\Delta}\ln\frac ba. \end{aligned} \]
Random radius: \(8t/\Delta\). Random order: \(1/k\). Protected inner centers: start the sum at \(a+1\).
If \(B(x,\Delta/8)=B(x,\Delta)\), then \(a=b\) and \[\Pr[B(x,t)\nsubseteq P(x)]\leq0.\]
Every potentially relevant center is already close enough to contain \(B(x,t)\). The local ratio captures this protection exactly.
The radius must fall into a short interval before a fixed center can be a boundary witness: \[\Pr[R\in I_k]\leq 8t/\Delta.\]
The center must also beat all \(k-1\) nearer candidates in the permutation: \[\Pr[\text{first among }k]=1/k.\]
For \(n\geq2\) and \(t\leq\Delta/8\), \[\boxed{\Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t\ln n}{\Delta}.}\] At the scale used later, choose \[\rho=\frac{\phi}{64\ln n},\qquad \frac\phi4<\Delta\leq\frac\phi2.\] Then the failure probability is at most \(1/2\).
Reconstruct the proof from these four lines:
Random trees: keep the local growth ratio \(\ln(b/a)\). Across scales, logarithmic growth terms telescope.
Euclidean embeddings: use \(\ln(b/a)\leq\ln n\). A protected ball and independent cluster coins create a separating coordinate.
For a current set \(S\):
Child labels are at most half the parent label. At the least common ancestor of \(x,y\), the label is at least \(d(x,y)\).
Every \(n\)-point metric admits a random noncontracting \(2\)-HST embedding with \[\boxed{\mathbb E[d_T(x,y)]\leq24\ln n\,d(x,y)}\] for each fixed pair \(x,y\).
This is an expected guarantee for each pair, not a claim that one sampled tree simultaneously has logarithmic distortion on every pair.
Write \(t=d(x,y)\) and \(n_i=|B(x,2^i)|\). The notes seek scale charges of the form \[2^i\cdot\frac{8t}{2^i}\ln\frac{n_i}{n_{i-3}}.\] The algebraic gain is \[\sum_{i=j}^{0}\ln\frac{n_i}{n_{i-3}}\leq3\ln n.\]
The ratio spans three dyadic levels: most logarithms cancel. This explains why the local FRT bound matters.
Let \(C^*\) be optimal for the original metric and let \(C_T\) be optimal for \(d_T\). For each \(p\), fix a nearest original center \(c^*(p)\in C^*\).
\[ \begin{aligned} \operatorname{cost}_d(C_T) &\leq\operatorname{cost}_{d_T}(C_T)\\ &\leq\operatorname{cost}_{d_T}(C^*)\\ &\leq\sum_{p\in X}d_T(p,c^*(p)). \end{aligned} \]
By linearity of expectation and the tree theorem, \[ \begin{aligned} \mathbb E[\operatorname{cost}_d(C_T)] &\leq\sum_{p\in X}\mathbb E[d_T(p,c^*(p))]\\ &\leq24\ln n\sum_{p\in X}d(p,c^*(p))\\ &=24\ln n\,\operatorname{OPT}_d. \end{aligned} \]
The notes conclude a polynomial-time algorithm with expected \(O(\log n)\) approximation.
At each scale, sample a partition and independently toss one fair coin per cluster. Let \(V\) be the union of clusters whose coins are tails.
For a nonempty \(Y\subseteq X\), set \(f(x)=d(x,Y)\). If \(y'\in Y\) is nearest to \(y\), then \[f(x)\leq d(x,y')\leq d(x,y)+d(y,y')=d(x,y)+f(y).\] Swap \(x\) and \(y\): \[\boxed{|f(x)-f(y)|\leq d(x,y).}\]
\[\Phi=\frac{\operatorname{diam}(X)}{\min_{x\ne y}d(x,y)}.\] Normalize the smallest distance to \(1\). Set \[\alpha=1+\lceil\lg\Phi\rceil,\qquad \beta=\lceil640\ln n\rceil.\]
The notes’ construction gives dimension \(\alpha\beta\) and distortion \[O(\sqrt\alpha\ln n).\] For \(\Phi\geq2\), these are \(O(\ln\Phi\ln n)\) and \(O(\sqrt{\ln\Phi}\ln n)\).
\[r_i=2^{i-2},\qquad 1\leq i\leq\alpha,\quad1\leq j\leq\beta.\] Sample a diameter-\(r_i\) partition \(P_{i,j}\) and its cluster coins. Let \(V_{i,j}\) be the union of tails clusters, and define \[f_{i,j}(x)=d(x,X\setminus V_{i,j}).\]
If \(V_{i,j}=X\), use the constant-zero coordinate. This convention makes every coordinate finite and nonexpansive.
\[F(x)=\bigl(f_{1,1}(x),\ldots,f_{1,\beta}(x),\ldots, f_{\alpha,1}(x),\ldots,f_{\alpha,\beta}(x)\bigr).\] There are \(\alpha\beta\) coordinates, each nonexpansive. Hence \[\boxed{\|F(x)-F(y)\|_2\leq\sqrt{\alpha\beta}\,d(x,y).}\]
Fix \(x\ne y\), with \(\phi=d(x,y)\). Choose \(u\) so that \[r_u\leq\phi/2<2r_u,\qquad\text{thus }\phi/4<r_u\leq\phi/2.\] Since cluster diameters are at most \(r_u<\phi\), \(x\) and \(y\) lie in different clusters.
Set \(\rho=\phi/(64\ln n)\). The FRT lemma gives \[\Pr[B(x,\rho)\subseteq P_{u,j}(x)]\geq1/2.\]
Use the event \[E_j=\{B(x,\rho)\subseteq P_{u,j}(x),\ x\in V_{u,j},\ y\notin V_{u,j}\}.\] Conditioned on any partition, the distinct clusters of \(x,y\) have independent coins: \[\Pr[E_j]\geq\frac12\cdot\frac12\cdot\frac12=\frac18.\]
On \(E_j\), the whole ball \(B(x,\rho)\) lies in \(V_{u,j}\), while \(y\) lies outside. Therefore \[f_{u,j}(x)\geq\rho,\qquad f_{u,j}(y)=0,\] \[|f_{u,j}(x)-f_{u,j}(y)|\geq\rho.\]
This is exactly where padding becomes a lower bound on an embedding distance.
Let \(Z=\sum_{j=1}^{\beta}\mathbf1[E_j]\). The trials are independent and \[\mu=\mathbb E[Z]\geq\beta/8.\] The Chernoff estimate used in the notes gives \[\Pr[Z<\beta/16]\leq\Pr[Z<\mu/2] \leq e^{-\mu/8}\leq e^{-\beta/64}\leq n^{-10}.\]
With probability at least \(1-n^{-10}\) for this pair, \[\|F(x)-F(y)\|_2\geq\rho\sqrt{\beta/16} =\frac{\sqrt\beta}{256\ln n}\,d(x,y).\] Set \(G=(256\ln n/\sqrt\beta)F\). Then \[d(x,y)\leq\|G(x)-G(y)\|_2 \leq256\sqrt\alpha\ln n\,d(x,y).\]
There are \(\binom n2\) unordered pairs. A union bound gives \[\Pr[\text{some pair fails}]\leq\binom n2n^{-10}<n^{-8}.\]
The notes propose checking all pairwise distortions and restarting if necessary. Thus the bounded-spread construction succeeds with high probability.
The bounded-spread dimension depends on \(\ln\Phi\). With arbitrarily many scales, there are two problems:
The notes propose ignoring very short distances at each scale and capping the coordinate values at \(2r_i\).
At scale \(r_i\), join pairs with \(d(x,y)\leq r_i/n^2\). Each connected component has diameter at most \(r_i/n\). The notes propose intercomponent distances \[d_i(C,C')=\min_{x\in C,\,y\in C'}d(x,y).\]
This minimum-distance formula need not satisfy the triangle inequality. The notes’ “Partition induced metric” exercise explicitly asks for a counterexample. Thus the subsequent argument is a proof outline, not a complete proof as written.
For a fixed pair at distance \(\phi\), the notes organize the blocks as follows:
| Scale | Intended contribution |
|---|---|
| \(r_i>\phi n^2\) | Identical coordinates |
| \(\phi/n^2\leq r_i\leq\phi n^2\) | \(O(\log n)\) relevant scales |
| \(r_i<\phi/n^2\) | Geometric tail, using the cap \(2r_i\) |
The intended upper bound is \(O(\phi\sqrt{\beta\log n})\), leading to distortion \(O(\log^{3/2}n)\) with the earlier lower bound.
Low quality Bourgain theorem. Every \(n\)-point metric embeds into \(\mathbb R^{n-1}\) with distortion \[\boxed{O(\log^{3/2}n).}\] The notes also state that Johnson–Lindenstrauss reduces the dimension to \(O(\log n)\).
Once a finite Euclidean embedding is obtained, its \(n\) image points lie in an affine subspace of dimension at most \(n-1\), preserving all their distances.
\[\operatorname{diam}(C)\leq\Delta,\qquad \Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t}{\Delta}\ln\frac ba.\]
For trees: local growth across scales.
For Euclidean coordinates: a protected ball, two cluster coins, and repetition.
For clustering: noncontraction plus a per-pair expected tree bound.
Clustering for HST: obtain the \(O(k^2n)\) algorithm. Hint from the notes: transform to a binary tree, then use dynamic programming.
Partition induced metric: give a counterexample to the minimum-distance formula being a metric for an arbitrary partition.
Diameter via embeddings: use \(O(1/\sqrt\varepsilon)\) planar projections to obtain a \((1-\varepsilon)\) diameter approximation in \(O(n/\sqrt\varepsilon)\) time.
CS 574 · Finite metric spaces and partitions · Notes 42