In yesterday’s post, I wrote up the beginning of Assaf Naor’s Banff talk on superexpanders. However, I never defined a superexpander. Let’s rectify that now.
Definition A superexpander is a sequence of graphs (3-regular, by our simplifying assumptions) which is an expander with respect to any uniformly convex Banach space.
Remember that a uniformly convex Banach space is one in which the midpoint of any line segment, whose endpoints are on the unit sphere, lies “uniformly deep” in the unit ball – the implied uniform control being in terms of the length of the line segment. A space that has an equivalent uniformly convex norm is called superreflexive, whence the “super” in superexpander.
Kasparov and Yu proved the coarse Baum-Connes conjecture for metric spaces that coarsely embed into a uniformly convex space. Just as ordinary expanders yield metric spaces that can’t be coarsely embedded into Hilbert space, superexpanders yield spaces that can’t be coarsely embedded into uniformly convex spaces. The first examples of superexpanders were produced by Lafforgue using his work on “strong T”; they are box spaces associated to \( SL(3,{\mathbb Q}_p)\). . A consequence of the Mendel-Naor work is a new construction of superexpanders. Naor did not give any details of this, but from their paper, it is an induction using the zig-zag product of graphs.
Naor formulated the expander condition in the following suggestive way: to say that \(G_n\) is an expander with respect to \(X\) is to say that the \(G_n\) (or maybe their coarse disjoint union) is “orthogonal” to \(X\) in some metric sense. Now let \(G_n\) be the specific superexpander that Mendel-Naor construct. They can now prove that \(G_n\) is almost surely “orthogonal”, in this metric sense, to a random sequence of graphs \(X_n\). This led him to speculate that a random graph will not be a superexpander – which, if true, would be a striking contrast to the principle that a random graph ought to be as expansive as you can get.
Writing this, it seems to me the natural question is to ask whether two independent (sequences of) random graphs are almost surely “orthogonal” in this sense. If so, the result for the specific superexpander \(G_n\) might not be so surprising
References
Lafforgue, Vincent. 2008. “Un renforcement de la propriété (T).” Duke Mathematical Journal 143(3):559–602. Retrieved August 23, 2013.
Kasparov, Gennadi, and Guoliang Yu. 2006. “The coarse geometric Novikov conjecture and uniform convexity.” Advances in Mathematics 206(1):1–56. Retrieved April 29, 2010.
Mendel, Manor, and Assaf Naor. n.d. “Nonlinear spectral calculus and super-expanders.” Publications mathématiques de l’IHÉS 1–95. Retrieved August 8, 2013.
Reingold, Omer, Salil Vadhan, and Avi Wigderson. 2002. “Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders.” The Annals of Mathematics 155(1):157–187.