2009/10/11 by Manor Mendel, Assaf Naor · 1 citation
Mathematics · #math.CO #math.FA #math.MG #msc:05C12 #msc:05C50 #msc:46B85 #msc:51F99
published as SODA '10: Symposium on Discrete Algorithms (2010), 236-255 · 32 pages. Extended abstract. To be published (in abridged form) in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms 2010 (SODA '10)
Given a finite regular graph G=(V,E) and a metric space (X,dX), let gamma+(G,X) denote the smallest constant γ+>0 such that for all f,g:V→ X we have: (1)/(|V|2)∑x,y∈ V dX(f(x),g(y))2≤ (γ+)/(|E|) ∑xy∈ E dX(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 γ+(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 Gi=(Vi,Ei), with limi→ ∞ |Vi|=∞, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of Gi in any uniformly convex Banach space is Ω(log |Vi|), 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.