Expander families and their applications

This research paper was completed and submitted at Nipissing University, and is made freely accessible through the University of Toronto’s TSpace repositoryThis thesis is to provide a brief introduction to the mathematical theory of expander families and their applications. Throughout this paper we mainly deal with graphs with finitely many vertices and edges. The central notion of this thesis is that of expansion roughly meaning the quality of a graph as a communication network where the vertices represent entities and an edge connects two vertices. An ideal communication network is a large graph with large isoperimetric constant, meanwhile the number of the edges are not too large. Cayley graphs are constructed from groups and they play a very important role in expander families. The second largest eigenvalue, the isoperimetric constant, and the diameter are the main measures of the expansion quality of Cayley graphs. The "zig-zag product" provides a straightforward combinatorial method to construct expander families