## Notes of Manor Mendel’s talk

Poincaré inequalities for expander graphs

Joint work with Assaf Naor.

1. Expanders

Say a ${d}$-regular graph is an ${\epsilon}$-expander if every subset ${S}$ of vertices, ${|S|\leq n/2}$, has conductance ${\frac{n|E(S,V\setminus S)|}{d|S||V\setminus S|}\geq\epsilon}$. Equivalently, for every function ${f:V\rightarrow\{ 0,1 \}}$,

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_{u,v}|f(u)-f(v)|\leq\frac{1}{\epsilon}\mathop{\mathbb E}_{\mathrm{edges}\,uv}|f(u)-f(v)|. \end{array}$

This is again equivalent to the same inequality, with the same constant, holding for all real valued functions ${f}$, or for all ${L_1}$-valued maps ${f}$. In this form, it is called the ${L_1}$-Poincaré inequality.

1.1. Expansion and embeddings

Theorem 1 (Bourgain) Every ${n}$-point metric space admits an embedding into ${\ell_1}$ with ${O(\log n)}$ distorsion.

This is sharp, as observed by Linial, London and Rabinovich, for expanders. Indeed, in a ${d}$-regular graph, pairwise distances are ${\geq\Omega(\log n)}$ in average.

1.2. ${L_1}$ versus ${L_p}$ Poincaré inequality

It is well-known that, for ${d}$-regular graphs, expansion is equivalent to a spectral gap. This is case ${p=2}$ in the following result.

Proposition 2 (Matousek) If graph ${G}$ satifies an ${L_1}$-Poincaré inequality

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_{u,v}|f(u)-f(v)|\leq\frac{1}{\epsilon}\mathop{\mathbb E}_{\mathrm{edges}\,uv}|f(u)-f(v)|, \end{array}$

then it satisfies for all ${p}$ an ${L_p}$-Poincaré inequality

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_{u,v}|f(u)-f(v)|^p\leq C(p,\epsilon)\mathop{\mathbb E}_{\mathrm{edges}\,uv}|f(u)-f(v)|^p . \end{array}$

Further generalizations by [Ozawa, Pisier].

1.3. More general Banach spaces

Definition 3 A Banach space ${X}$ is uniformly convex if

${X}$ is ${B}$-convex if does not uniformly contain Hamming cubes (or ${\ell_1^n}$).

${X}$ has finite cotype if it does not uniformly contain ${\ell_{\infty}^{n}}$.

Question: Does any expander satisfy Poincaré inequality with respect to every uniformly convex space ? Every Banach space of finite cotype ? This would be the most optimistic conjecture, since no space can satisfy Poincaré inequality with respect to ${\ell_{\infty}}$.

Theorem 4 (Lafforgue 2006, Mendel, Naor 2010) There exist families of graphs which satisfy a uniform ${X}$-valued Poincaré inequality for ${X}$ in the class of ${K}$-convex Banach spaces.

2. Different target spaces give rise to different notions of expansion

Theorem 5 (Mendel, Naor 2010) There exist a ${CAT(0)}$ metric space ${X}$ and two families of expanders ${G_i}$ and ${Z_j}$ such that

1. ${G_i}$ embed in ${X}$ with bounded distorsion;
2. ${Z_j}$ satisfies an ${X}$-valued Poincaré inequality.

In particular, ${Z_j}$ satisfies a ${G_i}$-valued Poincaré inequality. Think of ${CAT(0)}$ as the strongest form of convexity existing for non linear spaces: ${CAT(0)\cap}$Banach${=}$Hilbert.

2.1. Constructing ${Z_j}$

We use Reingold, Vadhan and Wigderson’s zig-zag product ${G}$, ${H\mapsto G\otimes H}$. As they did, we combine it with the power construction ${G\mapsto G^t}$.

The main feature they prove is

$\displaystyle \begin{array}{rcl} 1-\lambda(G\otimes H) \geq (1-\lambda(G))(1-\lambda(H)), \end{array}$

which I reformulate in terms of the constant ${\gamma}$ in the ${L_2}$-Poincaré inequality:

$\displaystyle \begin{array}{rcl} \gamma(G\otimes H,L_2) \leq\gamma(G,L_2)\gamma(H,L_2). \end{array}$

Combined with the easy ${\lambda(G^t)=\lambda(G)^t}$, i.e.

$\displaystyle \begin{array}{rcl} \gamma(G^t ,L_2)\leq O(\max\{\frac{1}{t}\gamma(G,L_2),1\}), \end{array}$

this gives expansion.

Poincaré inequalities naturally pass through zig-zag products.

Proposition 6 Whatever the target metric space ${X}$ be,

$\displaystyle \begin{array}{rcl} \gamma(G\otimes H,X) \leq\gamma(G,X)\gamma(H,X). \end{array}$

Powers are harder to deal with.

2.2. Powers

We give axioms on a target metric space for Poincaré inequalities to behave well under powers of graphs.

Definition 7 Let ${X}$ be a metric space. Assume we have a notion of center of mass ${CM(\mu)}$ for probability measures on ${X}$. Say that ${X}$ is ${p}$-barycentric if

1. For all probability measures ${\mu}$, ${\nu}$,
$\displaystyle \begin{array}{rcl} d_X (CM(\mu),CM(\nu))\leq C_1 W_1 (\mu,\nu), \end{array}$

where ${W_1}$ denotes transportation cost.

2. For all ${\mu}$ and ${x\in X}$,
$\displaystyle \begin{array}{rcl} d_X (x,CM(\mu))^p +C_2 \int d_X (CM(\mu),y)^p \,d\mu(y) \leq \int d_X (x,y)^p \,d\mu(y). \end{array}$

Example 1 Uniformly convex Banach spaces, ${CAT(0)}$ spaces are ${p}$-barycentric.

2.3. Martingales

Let ${\mathcal{F_0}\subset\cdots\subset\mathcal{F_m}}$ be ${\sigma}$-algebras, let ${\mu_{i-1}=CM(\mu_i |\mathcal{F}_{i-1})}$.

Pisier’s martingale cotype inequality

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E} d_X (\mu_m ,\mu_0)\geq C\,\sum_{i=0}^{m}\mathop{\mathbb E} d_X (\mu_i ,\mu_{i+1})^p . \end{array}$

characterizes uniform convexity among Banach spaces.

We use a non linear generalization, Keith Ball’s Markov cotype inequality. It does not directly imply

$\displaystyle \begin{array}{rcl} \gamma(G^t ,X)\leq O(\max\{\frac{1}{t}\gamma(G,X),1\}), \end{array}$

one needs replace ${G^t}$ with the Cesaro mean ${\frac{1}{t}\sum_{i=0}^{t}G^i}$.

Arora, Lovacs, Newman, Rabani, Rabinovich, Vempala show that there exist expanders with high girth, and anu subset of size ${\sqrt{n}}$ can be embedded in ${L^1}$ with bounded distorsion. We power and zig-zag from such graphs.

Kondo observed that the cone over a high girth graph is ${CAT(0)}$. This is the basic step of our construction of ${CAT(0)}$ space ${X}$.