An expander is a special sort of GRAPH [III.34] that has remarkable properties and many applications. Roughly speaking, it is a graph that is very hard to disconnect because every set of vertices in the graph is joined by many edges to its complement. More precisely, we say that a graph with n vertices is a c-expander if for every m ≤ n and every set S of m vertices there are at least cm edges between S and the complement of S.
This definition is particularly interesting when G is sparse: in other words, when G has few edges. We shall concentrate on the important special case where G is