Poincaré inequalities for expander graphs
Joint work with Assaf Naor.
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 3 A Banach space is uniformly convex if
is -convex if does not uniformly contain Hamming cubes (or ).
has finite cotype if 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.
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 6 Whatever the target metric space be,
Powers are harder to deal with.
We give axioms on a target metric space for Poincaré inequalities to behave well under powers of graphs.
Definition 7 Let be a metric space. Assume we have a notion of center of mass for probability measures on . Say that is -barycentric if
- For all probability measures , ,
where denotes transportation cost.
- For all and ,
Example 1 Uniformly convex Banach spaces, spaces are -barycentric.
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.