Cayley graphs of symmetric groups can form explicit family of bounded-degree expanders

You need to know: Graph, graphs of bounded degree, group, symmetric group (group of permutations of n symbols), notation for the number of elements in a finite set .

Background: For a graph , let , where the minimum is over subsets S of vertices of , and is the number of edges between S and its complement. An infinite family of graphs is a family of -expanders if for all n.

A generating set of a group G is a subset such that every can be written as a finite product of elements of S and their inverses. The (undirected) Cayley graph is the graph whose vertices are elements of G, and vertices are connected by edge if or for some .

The Theorem: On 28th May 2005, Martin Kassabov submitted to arxiv a paper in which he proved the existence of universal constants L and such that the following holds. For every n there exists a generating set of size at most L of the symmetric group such that the Cayley graphs form a family of -expanders.

Short context: Constructing explicit families of expanders is important, for example, for algorithmic applications. Although there are some combinatorial constructions, more traditional method is based on Cayley graphs of groups. Given an infinite family of finite groups, the problem is to construct generating sets to make their Cayley graphs expanders. The Theorem solves this problem for symmetric groups.  

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems