15
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I really like this question! $\endgroup$
    – Suvrit
    Nov 2, 2013 at 4:31
  • $\begingroup$ but do we have examples of expanders and CAT(0) spaces into which they do embed? $\endgroup$
    – Suvrit
    Nov 4, 2013 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$ Nov 4, 2013 at 17:44

3 Answers 3

11
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Welcome to MO, Manor! $\endgroup$
    – Gil Kalai
    Nov 4, 2013 at 19:08
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\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$ Nov 2, 2013 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.