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

Start Free Trial

No credit card required