# Superexpanders

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.