Skip to main content
added 267 characters in body
Source Link

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.

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

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.

Source Link

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