Mathematics – Metric Geometry
Scientific paper
2009-10-11
SODA '10: Symposium on Discrete Algorithms (2010), 236-255
Mathematics
Metric Geometry
32 pages. Extended abstract. To be published (in abridged form) in the proceedings of the ACM-SIAM Symposium on Discrete Algor
Scientific paper
Given a finite regular graph G=(V,E) and a metric space (X,d_X), let $gamma_+(G,X) denote the smallest constant $\gamma_+>0$ such that for all f,g:V\to X we have: \frac{1}{|V|^2}\sum_{x,y\in V} d_X(f(x),g(y))^2\le \frac{\gamma_+}{|E|} \sum_{xy\in E} d_X(f(x),g(y))^2. In the special case X=R this quantity coincides with the reciprocal of the absolute spectral gap of $G$, but for other geometries the parameter \gamma_+(G,X), which we still think of as measuring the non-linear spectral gap of G with respect to X (even though there is no actual spectrum present here), can behave very differently. Non-linear spectral gaps arise often in the theory of metric embeddings, and in the present paper we systematically study the theory of non-linear spectral gaps, partially in order to obtain a combinatorial construction of super-expander -- a family of bounded-degree graphs G_i=(V_i,E_i), with \lim_{i\to \infty} |V_i|=\infty, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of G_i in any uniformly convex Banach space is \Omega(\log |V_i|), which is the worst possible behavior due to Bourgain's embedding theorem. Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue. Our construction is different and combinatorial, relying on the zigzag product of Reingold-Vadhan-Wigderson.
Mendel Manor
Naor Assaf
No associations
LandOfFree
Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract] does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract], we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract] will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-463792