Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract]

الأصل · EN

Given a finite regular graph G=(V,E) and a metric space (X,dₓ), let gamma+(G,X) denote the smallest constant γ+>0 such that for all f,g:V→ X we have: 1/|V|²∑ₓ,y∈ ᵥ dₓ(f(x),g(y))²≤ γ+/|E| ∑xy∈ E dₓ(f(x),g(y))². 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 Gᵢ=(Vᵢ,Eᵢ), with ᵢ→ ∞ |Vᵢ|=∞, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of Gᵢ in any uniformly convex Banach space is Ω(|Vᵢ|), 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.