Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 155 / 3 / Solution

The Bourgain embedding theorem states that every $n$-point metric space embeds into a Hilbert space with distortion at most $C\log n$; the random-subset construction may be taken to have dimension $O((\log n{)}^2)$.

We use the following finite Frechet embedding lemma. For every integer $q\ge 2$, an $n$-point metric space $X$ has subsets $A_1,\dots ,A_k$ such thatand, for every $x,y\in X$, some $A_i$ satisfiesHere is the probabilistic proof. Put $\vartheta =n^{-1/q}$. For every level $i=1,\dots ,q$, independently formrandom subsets $A_{i,j}$ by including each point with probability $p_i=\min \{1/2,n^{-i/q}\}$.

Fix $x,y$ and put $\Delta =d(x,y)/(2q-1)$. Form $q+1$ open balls $B_0,\dots ,B_q$ by taking $B_t$ to have radius $t\Delta$ and center $x$ for even $t$ and $y$ for odd $t$. Consecutive balls are disjoint because their radii sum to at most $(2q-1)\Delta =d(x,y)$. Partition the cardinality interval $[1,n]$ intoAmong the $q+1$ cardinalities $|B_t|$, either two consecutive ones lie in one interval, or some consecutive pair decreases. In either case there are $i,t$ such that, after orienting the pair appropriately,At level $i$, a random set hits $B_t$ with probability at least $\vartheta /3$ and misses the disjoint $B_{t+1}$ with probability at least $1/4$. These events are independent, and when both occur the two distance-to-set values differ by at least $\Delta$. Thus one sample succeeds with probability at least $\vartheta /12$. All $m$ samples at that level fail with probability at mostA union bound over the fewer than $n^2/2$ unordered pairs leaves a simultaneous successful choice. There are $qm\le Cq{n}^{1/q}\log n$ coordinates, proving the lemma.

DefineEvery distance-to-set coordinate is one-Lipschitz, while the lemma supplies the lower bound. Henceproving the Low-dimensional Frechet embedding into linfinity.

Take $q=\lceil \log n\rceil$. Then $n^{1/q}\le e$, $k=O((\log n{)}^2)$, and the distortion into ${\ell }_{\infty }^k$ is $O(\log n)$. Sincethe identity ${\ell }_{\infty }^k\to {\ell }_2^k$ has distortion $O(\log n)$. Composition gives

Finally let a $d$-regular expander $G$ embed into ${\ell }_{\infty }^k$ with distortion at most $\alpha$. For $1<p<\infty$, the identityhas distortion at most $k^{1/p}$. Therefore the assumed lower bound givesFor $k\ge e^2$, choose $p=\log k$, so $k^{1/p}=e$ andAdjusting the constant handles bounded $k$, and exponentiation proves the Dimension lower bound for an expander embedded in linfinitywhere $c>0$ depends only on $d$ and $h$.