A last-minute extra talk was scheduled on the Wednesday morning at the Banff meeting – Assaf Naor on Superexpanders.  I would have loved to attend that talk, but I had a prior commitment to Aftenroe, a beautiful eight-pitch limestone climb above the road to Lake Louise.

Fortunately, thanks to the video system at BIRS, this doesn’t mean that I missed the talk.   One can find the excellent video of the talk here.  It’s a great presentation, as gratifying and elegant as Aftenroe‘s third pitch.  Below, I will try to describe some of the ideas.

Assaf begins by recalling the classical definition of an expander sequence of graphs (for simplicity, all his expanders are sequences of 3-regular graphs).  It’s a sequence of finite graphs \(X_n\), of size tending to infinity, such that for each subset \(A\subseteq X_n\) comprising half the vertices or fewer, the size of the boundary of \(A\), that is the number of edges connecting \(A\) to its complement, is at least some uniform constant times the size of \(A\) itself.

Then he points out that this definition is equivalent to the following: for any map \(f\colon X_n\to {\mathbb R}^k \), and any \(p\in [1,\infty)\), one has

\[ \frac{1}{n^2} \sum_{(v,v’)\in V\times V} d(f(v),f(v’))^p \approx \frac{1}{n} \sum_{(v,v’)\in E} d(f(v),f(v’))^p. \]

Here \(V,E\) are the sets of vertices and edges respectively, and the \(\approx\) symbol means that each side is bounded (independent of \(n\)) by a constant multiple of the other.  The statements for various \(p\) are all equivalent.  Considering \(\{0,1\}\)-valued functions with \(k=p=1\) shows they imply the classical definition of expander; the \(k=1,\ p=2\) statement is just the “spectral gap” version of expansion; for \(p=2\), the \(k=1\) case trivially implies the arbitrary \(k\) case.  Notice that the force of the result is this: the average distance between a configuration of \(n\) points in Euclidean space can be effectively computed just by sampling the distances along a suitable group of \(O(n)\) edges.

Anyhow, from this perspective there is an obvious question: what is so special about Euclidean space?  In fact, let \(X\) be any metric space.  Call a sequence of 3-regular graphs an expander with respect to \(X\) if

\[ \frac{1}{n^2} \sum_{(v,v’)\in V\times V} d(f(v),f(v’))^2 \approx \frac{1}{n} \sum_{(v,v’)\in E} d(f(v),f(v’))^2 \]

where now \(f\) runs over maps from \(X_n\) to \(X\).  It is easy to see that:

• Whenever \(X\) has at least two points, a sequence that is an expander wrt \(X\) is also an expander in the classical sense.
• No sequence of graphs (of size tending to infinity) is an expander wrt itself, and (as a consequence) no sequence is an expander wrt \(X=\ell^\infty\).

The whole machinery can be generalized by introducing a nonlinear spectral theory.  Let \(K\) be a symmetric kernel on some set \(X\) (think of the metric, or some power thereof, on a metric space). Let \(A\) be an \(n\times n\) symmetric stochastic matrix (think of the normalized adjacency matrix of a regular graph).  Then define the nonlinear Poincare constant of \(A\) with respect to \(K\), denoted \(\gamma(A,K)\), to be the best (infimal) constant \(\gamma\) for which the following inequality holds for all \(n\)-tuples \(x_1,\ldots,x_n\in X\):

\[ \frac{1}{n^2} \sum_{i,j=1}^n  K(x_i,x_j) \le \frac{\gamma}{n} \sum_{i,j=1}^n a_{ij}K(x_i,x_j). \]

Then the graphs \(X_n\) are expanders wrt \(X\) if the Poincare constants of their normalized adjacency matrices, with respect to the kernel \(d^2\) on \(X\),  are bounded away from zero.

I’ll continue the discussion in the next post.

References

Mendel, Manor, and Assaf Naor. “Nonlinear Spectral Calculus and Super-expanders.” Publications Mathématiques de l’IHÉS (n.d.): 1–95. Accessed August 8, 2013. doi:10.1007/s10240-013-0053-2.