It is well-known that expanders are hard to embed into Hilbert (or $\ell^p$) spaces - any embedding of an expander with $n$ vertices has distortion $\Omega(\log n)$.

Can anyone provide a reference (or a quick argument) that the same holds for any "nice" CAT(0) space (like the hyperbolic space) instead of Hilbert space? I'm not giving a precise definition of "nice" here, but this is discussed e.g. in Gromov's "Random Walk in Random Groups".

  • $\begingroup$ I really like this question! $\endgroup$ – Suvrit Nov 2 '13 at 4:31
  • $\begingroup$ but do we have examples of expanders and CAT(0) spaces into which they do embed? $\endgroup$ – Suvrit Nov 4 '13 at 17:42
  • 1
    $\begingroup$ @Suvrit: yes, see e.g. arxiv.org/abs/1306.5434 - Mendel and Naor construct a CAT(0) space that admits some expanders embedded bilipschitzly. $\endgroup$ – Marcin Kotowski Nov 4 '13 at 17:44

Here is a class of Hadamard spaces in which, I think, no expander embeds: Consider a Hadamard space $X$, which is also "FDSCBB" in the sense Burago, Gromov, and Perel'man (see http://seven.ihes.fr/~gromov/PDF/3[86].pdf section 7).

By Corollary 7.10 in [BGP] The tangent cone has non-negative curvature in Alexandrov sense. By Theorem 3.19 from [Bridson & Haeflinger] the tangent cone is also CAT(0), which together means it is Euclidean.

So given a finite subset $S\subset X$, let $x_0\in X$ be its center of mass.

Since the tangent cone around $x_0$ is Euclidean we can have a map into Hilbert space $f:S\cup\{x_0\} \to H$ such that $f(x_0)=0$ for every $s\in S$, $\|f(s)\|_2= d(x_0,s)$, and the angles in the image are preserved, .i.e. $\angle_0 (f(s),f(s')) = \angle_{x_0}(s,s')$ for every $s,s'\in S$.

The CAT(0) property implies that the mapping $f$ is 1-Lipschitz on $S$. $f$ also have the "average distortion property", i.e., $$ \sum_{s,s'\in S} \|f(s)-f(s')\|_2^2 \ge \frac14 \sum_{s,s'\in S} d(s,s')^2 .$$

Together this implies the ``Poincar\'e inequality" for any graph with respect to Hilbert space transfers to $X$ with a loss of factor of 4, see for example http://www.cims.nyu.edu/~naor/homepage%20files/spectral-compare.pdf page 5.

We are left prove the average distortion property of $f$. This is probably standard but since I'm not aware of it, I'll sketch the argument.

For $\lambda\in[0,1]$, denote by $\lambda S \subset X$ the subset where each $s\in S$ is replaced with the (unique) point $\lambda s$ which is of distance $\lambda d(x_0,s)$ from $x_0$ along the geodesic connecting $x_0$ and $s$. Observe that $x_0$ is also the center of mass of $\lambda S$. Define $f_\lambda:\lambda S\to H$ by $f_\lambda(\lambda s)=\lambda f(s)$. When $\lambda $ is small $f_\lambda$ preserves distances upto arbitrary precision times $\lambda$, and so, denoting $y_0$ the barycenter of $f_\lambda(\lambda S)$

$$ \sum_{s,s'\in S} \|f(s)-f(s')\|_2^2 =\lambda^{-2} \sum_{s,s'\in S} \|f_\lambda(\lambda s)-f(\lambda s')\|_2^2 = \lambda^{-2} 2|S| \sum_{s\in S} \|f_\lambda(\lambda s)-y_0\|_2^2 \ge \lambda^{-2} |S| \sum_{s\in S} \|f_\lambda(\lambda s)\|_2^2=|S| \sum_{s\in S} d(x_0,s)^2 \ge \frac14 \sum_{s,s'\in S} d(s,s')^2 .$$

Update: Upon reading the literature more carefully, similar arguments were done before. For example, Naor & Silberman In arXiv:1005.4084 have basically the same argument. See Proposition 4.9 and Corollary 4.10 there.

| cite | improve this answer | |
  • $\begingroup$ Welcome to MO, Manor! $\endgroup$ – Gil Kalai Nov 4 '13 at 19:08

I don't know if this is the type of result you are looking for, because it is less quantitative than in your question, but in - http://arxiv.org/pdf/1102.0729v2.pdf (in corollary 1.7), Toyoda proves that if $X$ is a geodesically complete CAT(0) space that has a group acting cocompactly and properly on it, then a family of expanders does not embed coarsely into $X$ (he actually proves a little more - check reference for exact statement).

| cite | improve this answer | |

See the recent preprint http://arxiv.org/abs/1306.5434 (Mendel and Naor).

| cite | improve this answer | |
  • $\begingroup$ I know this paper, it deals with a different situation, namely constructing a "wild" CAT(0) space and certain expanders with respect to it. But I'm asking about embedding classical expanders into CAT(0) spaces encountered in nature (like hyperbolic spaces or buildings). $\endgroup$ – Michal Kotowski Nov 2 '13 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.