Stochastic Construction of Expander Graphs

Expander graphs form a class of combinatorial objects that are used for many important constructions that are of interest in the theory of computation; their widespread applications range from error-correcting codes to pseudorandom number generators and switching networks. Yet until recently, constructions of the expander graphs themselves were either highly nontrivial or entirely random and unstructured. In their 2002 paper, Alon and Roichman proved that for every group G of order n, the Cayley graph with respect to O(logn) random elements almost always produces an expander. This stochastic construction provided a nice alternative to the previously known explicit, but sophisticated, constructions. It also avoided ineciencies due to local expansion deficiencies in the entirely randomized argument. However, their proof was fairly complex and derived its bound indirectly, through the use of an auxiliary inequality that related the second-largest (in absolute value) eigenvalue of the graph’s adjacency matrix to the probability that a random walk on the graph is closed. In this paper, we present a direct proof of the Abelian case of their result, using only elementary group representation theory (which, incidentally, is equivalent to Fourier analysis in our Abelian case). Furthermore, our representationtheoretic approach induces the stronger conjecture that only O(logR) generators are required, where R is the number of irreducible representations of G. This would yield an asymptotic improvement because there exist groups, such as the symmetric group, for which R is subpolynomial with respect to n.