Expander graph

Summary

An expander graph is a sparse graph in which every set of at most half of the vertices has many edges leaving it. One usually means a family of regular graphs of fixed degree whose Cheeger constant stays above a fixed positive bound. Expanders combine few edges with strong connectivity, and they are used in network design, error-correcting codes, derandomization and group theory.