October 2006 | SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON
Expander graphs are highly connected yet sparse graphs with significant structural properties. They appear in various fields, including computer science, mathematics, and physics. This survey explores the definition, properties, and applications of expander graphs. The key properties of expander graphs include expansion, which ensures that the graph is both sparse and highly connected. Expander graphs have been studied extensively, with their existence first proved by Pinsker in the early 1970s. They are useful in communication networks, error-correcting codes, and pseudorandomness. The study of expanders involves structural, explicit construction, and algorithmic problems. Expanders are also related to eigenvalues and spectral properties, with the spectral gap playing a crucial role in their analysis. The survey discusses various aspects of expanders, including their construction, applications in coding theory, and their role in randomness extraction. The text also covers the use of expanders in probabilistic algorithms, such as error amplification for RP. The survey is structured into several sections, covering topics such as graph expansion, eigenvalues, random walks, geometric views, extremal problems, and applications in coding theory. The authors emphasize the importance of expanders in both theoretical and practical contexts, highlighting their versatility and significance in various domains.Expander graphs are highly connected yet sparse graphs with significant structural properties. They appear in various fields, including computer science, mathematics, and physics. This survey explores the definition, properties, and applications of expander graphs. The key properties of expander graphs include expansion, which ensures that the graph is both sparse and highly connected. Expander graphs have been studied extensively, with their existence first proved by Pinsker in the early 1970s. They are useful in communication networks, error-correcting codes, and pseudorandomness. The study of expanders involves structural, explicit construction, and algorithmic problems. Expanders are also related to eigenvalues and spectral properties, with the spectral gap playing a crucial role in their analysis. The survey discusses various aspects of expanders, including their construction, applications in coding theory, and their role in randomness extraction. The text also covers the use of expanders in probabilistic algorithms, such as error amplification for RP. The survey is structured into several sections, covering topics such as graph expansion, eigenvalues, random walks, geometric views, extremal problems, and applications in coding theory. The authors emphasize the importance of expanders in both theoretical and practical contexts, highlighting their versatility and significance in various domains.