This is an announcement for the paper "Towards a calculus for non-linear spectral gaps [extended abstract]" by Manor Mendel and Assaf Naor.

Abstract: 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.

Archive classification: math.MG math.CO math.FA

Mathematics Subject Classification: 51F99, 05C12, 05C50, 46B85

Remarks: 32 pages. Extended abstract. To be published (in abridged form) in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms 2010 (SODA '10)

The source file(s), , is(are) stored in gzipped form as with size . The corresponding postcript file has gzipped size .

Submitted from: mendelma@gmail.com

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/0910.2041

or

http://arXiv.org/abs/0910.2041

or by email in unzipped form by transmitting an empty message with subject line

uget 0910.2041

or in gzipped form by using subject line

get 0910.2041

to: math@arXiv.org.