Expanders and Diffusers

Abstract

Expander graphs are ingredients for making concentrating, switching, and sorting networks, and are closely related to sparse, doubly-stochastic matrices called diffusers. The best explicit examples of diffusers are defined by means of the action of elements of the matrix group $SL (2,{\bf Z} )$ on certain finite mathematical objects. Some corresponding, explicit expanders were introduced by Margulis. However, Gabber and Galil were the first to obtain good estimates for the expanders and produce from them a family of directed acyclic superconcentrators having density 271.8. In this paper we review various techniques for making expanders from diffusers. We also demonstrate asymptotic upper bounds on the strength of algebraically defined classes of degree k diffusers. Each upper bound is given as the norm of a diffusion operator on an infinite discrete group, and bounds for several examples are calculated. Numerical evidence is supplied in support of our conjecture that these bounds can be achieved by certain algebraically defined examples. The conjecture, if true, would lead to superconcentrators of density less than 58.