**Poincaré inequalities for expander graphs**

Joint work with Assaf Naor.

**1. Expanders **

Say a -regular graph is an -expander if every subset of vertices, , has conductance . Equivalently, for every function ,

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

** 1.1. Expansion and embeddings **

Theorem 1 (Bourgain)Every -point metric space admits an embedding into with distorsion.

This is sharp, as observed by Linial, London and Rabinovich, for expanders. Indeed, in a -regular graph, pairwise distances are in average.

** 1.2. versus Poincaré inequality **

It is well-known that, for -regular graphs, expansion is equivalent to a spectral gap. This is case in the following result.

Proposition 2 (Matousek)If graph satifies an -Poincaré inequality

then it satisfies for all an -Poincaré inequality

Further generalizations by [Ozawa, Pisier].

** 1.3. More general Banach spaces **

Definition 3A Banach space isuniformly convexif

is-convexif does not uniformly contain Hamming cubes (or ).

hasfinite cotypeif it does not uniformly contain .

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

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

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

Theorem 5 (Mendel, Naor 2010)There exist a metric space and two families of expanders and such that

embed in with bounded distorsion;satisfies an -valued Poincaré inequality.

In particular, satisfies a -valued Poincaré inequality. Think of as the strongest form of convexity existing for non linear spaces: BanachHilbert.

** 2.1. Constructing **

We use Reingold, Vadhan and Wigderson’s zig-zag product , . As they did, we combine it with the power construction .

The main feature they prove is

which I reformulate in terms of the constant in the -Poincaré inequality:

Combined with the easy , i.e.

this gives expansion.

Poincaré inequalities naturally pass through zig-zag products.

Proposition 6Whatever the target metric space be,

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 7Let be a metric space. Assume we have a notion of center of mass for probability measures on . Say that is-barycentricif

For all probability measures , ,

where denotes transportation cost.For all and ,

Example 1Uniformly convex Banach spaces, spaces are -barycentric.

** 2.3. Martingales **

Let be -algebras, let .

Pisier’s martingale cotype inequality

characterizes uniform convexity among Banach spaces.

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

one needs replace with the Cesaro mean .

Arora, Lovacs, Newman, Rabani, Rabinovich, Vempala show that there exist expanders with high girth, and anu subset of size can be embedded in with bounded distorsion. We power and zig-zag from such graphs.

Kondo observed that the cone over a high girth graph is . This is the basic step of our construction of space .

The slides of this talk can be downloaded here.