O'Reilly logo

The Princeton Companion to Mathematics by Imre Leader, June Barrow-Green, Timothy Gowers

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

III.24 Expanders

Avi Wigderson

1 The Basic Definition

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 mImagen 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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required