Nonlinear spectral calculus and super-expanders (Q2249432): Difference between revisions

Let \(A=(a_{ij})_{i,j=1}^n\) be a symmetric stochastic matrix, \( 1=\lambda_1(A)\geq \lambda_2(A)\geq\dots\geq \lambda_n(A)\geq -1\) be its eigenvalues. The spectral gap of \(A\) is defined as \(1-\lambda_2(A)\). The starting point of the paper is following a far-reaching generalization of this notion. For \(p\in [1,\infty)\) and a metric space \((X,d_X)\), the reciprocal nonlinear spectral gap \(\gamma(A,d_X^p)\) of \(A\) with respect to \(X\) is the infimum over those \(\gamma\in (0,\infty]\) for which all \(x_1,\dots,x_n\in X\) satisfy \[ \frac{1}{n^2} \sum_{i=1}^n\sum_{j=1}^n d_X(x_i,x_j)^p\leq \frac{\gamma}{n}\sum_{i=1}^n\sum_{j=1}^n a_{ij} d_X(x_i,x_j)^p. \] One can verify that \(1-\lambda_2(A)=1/\gamma(A,d_X^2)\), where \((X,d_X)\) is either the real line or a Hilbert space (with the standard metric). Some of the results of the authors hold even in the case where \(X\) is any set and \(d_X(x_i,x_j)^p\) is replaced by \(K(x_i,x_j)\), where \(K:X\times X\to[0,\infty)\) is any symmetric function. An immediate generalization of an observation of Gromov implies that a sequence of finite \(d\)-regular graphs \(\{G_i\}_{i=1}^\infty\) with normalized adjacency matrices \(\{A_i\}_{i=1}^\infty\), for which the nonlinear spectral gaps \(\{\gamma(A_i,d_X^p)\}_{i=1}^\infty\) are uniformly bounded, does not admit uniformly coarse embeddings into \((X,d_X)\) (uniformly coarse means: with the same lower and upper control functions). The present paper was motivated by the desire to find a construction of a family of expanders not admitting uniformly coarse embeddings into any uniformly convex Banach space (the authors call such expanders super-expanders), which would be algebraically less involved than the original construction of \textit{V. Lafforgue} [Duke Math. J. 143, No. 3, 559--602 (2008; Zbl 1158.46049)]. The value of this paper goes far beyond that. The authors have started to build a useful and rich theory of nonlinear spectral gaps. This includes: (1) The submultiplicativity of the absolute nonlinear spectral gap with respect to zigzag products (Theorem 1.3) (the word absolute is introduced because the authors had to modify the definition slightly, in the classical case this modification corresponds to replacing \(1-\lambda_2(A)\) by \(1-\max\{|\lambda_2(A)|,|\lambda_n(A)|\}\)). As a result, the authors get a substantially simpler than the original (see [\textit{O. Reingold} et al., Ann. Math. (2) 155, No. 1, 157--187 (2002; Zbl 1008.05101)]) proof of expanding propertied of zigzag products. The authors also prove similar results (Theorem 1.13) for other products of graphs: tensor product, derandomized square, replacement product, balanced replacement product. (2) To construct super-expanders following the iterative strategy of Reingold et al. [loc. cit.] for the construction of zigzag expanders, two more ingredients are needed: a base graph (a graph of fixed size with controlled nonlinear spectral gap) and spectral calculus, which replaces the simple observation about the absolute spectral gap of a power of a matrix. (For nonlinear spectral gaps, the spectral calculus is no longer simple.) To construct a suitable base graph, the authors combine the ``hypercube quotient argument'' of \textit{S. Khot} and \textit{A. Naor} [Math. Ann. 334, No. 4, 821--852 (2006; Zbl 1102.46051)] and the methods of \textit{G. Pisier} [Ann. Math. (2) 115, 375--392 (1982; Zbl 0487.46008)]. To develop a spectral calculus for nonlinear spectral gaps, the authors introduce a metric Markov cotype. The definition is rather technical, it is motivated by the Markov cotype \(2\) property of Banach spaces introduced by \textit{K. Ball} [Geom. Funct. Anal. 2, No. 2, 137--172 (1992; Zbl 0788.46050)]. Using this notion, the authors succeed to get results which suffice for the completion of their construction: (i) uniformly convex Banach spaces have metric Markov cotype (Theorem 6.10); (ii) a metric Markov cotype implies a suitable decay of the nonlinear spectral gaps of suitable substitutes for powers of a matrix (Lemma 3.1). The authors show (Remark 4.4) that their approach can be used to show that there exist bounded degree expanders which do not admit uniformly coarse embeddings into any \(K\)-convex Banach space. This answers the question asked by Lafforgue [loc. cit.]. The authors mention that Lafforgue has already answered the question modifying his argument [\textit{V. Lafforgue}, J. Topol. Anal. 1, No. 3, 191--206 (2009; Zbl 1186.46022)]. The authors also provide an example of two constant degree families \(\{G_i\}_{i=1}^\infty\) and \(\{H_i\}_{i=1}^\infty\) of expanders such that \(\{G_i\}\) does not admit uniformly coarse embeddings into \(\{H_i\}\) (Theorem 9.1). Everyone interested in the theory of expander graphs or the theory of metric embeddings will find interesting impressive results, handy tools, and food for thought in this paper. Reviewer's remark: The recent paper of the second author [Anal. Geom. Metr. Spaces 2, 1--52 (2014; Zbl 1316.46023)] contains further results on nonlinear spectral gaps.