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

The slides of this talk can be downloaded here.



About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s