[METRIC 2011] Manor Mendel

METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 24, 15:00-16:00 - Manor Mendel (Open U. Israel, Raanana)
Expanders families and Poincaré inequalities
---
The Poincaré inequality for a regular graph G=(V,E) says that in any mapping of the vertices into the real line f:V-->R, the average over all pairs x,y in V of |f(x)-f(y)|^2 is bounded from above by the average over all edges (x,y) in E of |f(x)-f(y)|^2 times reciprocal of the normalized spectral gap of G.

Motivated by its applications for proving non-embeddability results of expanders, Matousek extended the Poincaré inequality for graphs to L_p codomains, p