Combinatorics Seminar

When: Sunday, January 11, 10am Where: Schreiber 309 Speaker: Manor Mendel, Open University Title: Towards a calculus for non-linear spectral gaps

Abstract:

For a regular undirected graph G=(V,E), let g(G) be the largest positive number g such that for every f:V--> Reals,

AVERAGE_{x,y \in V} |f(x)-f(y)|^2 < g^{-1} AVERAGE_{(x,y)\in E} |f(x) - f(y)|^2.

It is known that g(G) is the (normalized) spectral gap of G, i.e. g(G)=1 - \lambda_2(G), where \lambda_2(G) is the normalized second eigenvalue of G. Motivated by questions on the embedability of expander graphs in more general metric spaces, we replace the Reals in the above definition with other metric spaces, and study the behavior of the resulting "non-linear spectral gap" under various operations.

We obtain the following results:

A clean and general analysis of the zigzag product of graphs, devoid of linear algebra;

A proof that spectral gap in barycentric spaces of a power of graph increases similarly to the classical spectral gap;

A high degree, yet non-trivial, family of graphs with constant spectral gap in B-convex Banach spaces. The graph is obtained by applying the noise (Bonami-Beckner) operator on the Hamming cube, and taking a quotient of it by the dual of a "good" linear code. The analysis is inspired by a construction of Khot and Naor and the proof of Pisier's K-convexity theorem.

The above results are applied to show a construction of constant degree zigzag expanders in uniformly convex Banach spaces. As a side benefit, we also obtain a Lipschitz extension theorem from subsets of L_p or series/parallel graphs into simply connected spaces of non-positive curvature.

No prior knowledge of the notions above will be assumed.

Joint work with Assaf Naor (NYU).