Expanders

Michael Nielsen has been writing a series of posts on expanders.

This post is one in a series introducing one of the deepest ideas in modern computer science, expander graphs. Expanders are one of those powerful ideas that crop up in many apparently unrelated contexts, and that have a phenomenally wide range of uses. The goal of the posts is to explain what an expander is, and to learn just enough about them that we can start to understand some of their amazing uses.

If you haven't been there to read them, do check them out. He starts off with basic definitions, gives some examples, relates expansion to adjacency matrices and the eigenvalue gap, and gives as an application the use of random walks on expanders to decrease randomness.