BULLETIN (New Series)OF THE AMERICAN MATHEMATICAL SOCIETY (00012 4.October 2006,Pages 439-561 Article electronically published on August 7,2006 EXPANDER GRAPHS AND THEIR APPLICATIONS SHLOMO HOORY.NATHAN LINIAL.AND AVI WIGDERSON An Overview A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists,since expander graphs,the protagonists of our story,come up in numerous and often surprising contexts in both fields. But,perhaps,we should start with a few words about graphs in general.They are,of course,one of the prime objects of study in Discrete Mathematics.However, graphs are among the most ubiquitous models of both natural and human-made structures.In the natural and social sciences they model relations among species, societies,companies,etc.In computer science,they represent networks of commu- nication,data organization,computational devices as well as the flow of computa- tion,and more.In mathematics,Cayley graphs are useful in Group Theory.Graphs carry a natural metric and are therefore useful in Geometry,and though they are "just"one-dimensional complexes,they are useful in certain parts of Topology,e.g. Knot Theory.In statistical physics,graphs can represent local connections between interacting parts of a system,as well as the dynamics of a physical process on such systems. The study of these models calls.then.for the comprehension of the significant structural properties of the relevant graphs.But are there nontrivial structural properties which are universally important?Expansion of a graph requires that it is simultaneously sparse and highly connected.Expander graphs were first de- fined by Bassalygo and Pinsker,and their existence first proved by Pinsker in the early'70s.The property of being an expander seems significant in many of these mathematical,computational and physical contexts.It is not surprising that ex- panders are useful in the design and analysis of communication networks.What is less obvious is that expanders have surprising utility in other computational settings such as in the theory of error correcting codes and the theory of pseudorandom- ness.In mathematics,we will encounter e.g.their role in the study of metric embeddings,and in particular in work around the Baum-Connes Conjecture.Ex- pansion is closely related to the convergence rates of Markov Chains,and so they play a key role in the study of Monte-Carlo algorithms in statistical mechanics and in a host of practical computational applications.The list of such interesting and fruitful connections goes on and on with so many applications we will not even Received by the editors April 28,2006,and,in revised form,May 10,2006. 2000 Mathematics Subject Classification.Primary 01-01,68-01,05-01,68Q01,94-01;Sec- ondary68Q15,68Q17,94B05.05C25,05C35,05C40,05C50,05C80.05C90,60J10.35J99,20F05 20F69.20C99. Work supported in part by grants from the Israel Science Foundation and the Israel-U.S Binational Fund. C2006 S.Hoory,N.Linial,and A.Wigderson 439BULLETIN (New Series) OF THE AMERICAN MATHEMATICAL SOCIETY Volume 43, Number 4, October 2006, Pages 439–561 S 0273-0979(06)01126-8 Article electronically published on August 7, 2006 EXPANDER GRAPHS AND THEIR APPLICATIONS SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON An Overview A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists, since expander graphs, the protagonists of our story, come up in numerous and often surprising contexts in both fields. But, perhaps, we should start with a few words about graphs in general. They are, of course, one of the prime objects of study in Discrete Mathematics. However, graphs are among the most ubiquitous models of both natural and human-made structures. In the natural and social sciences they model relations among species, societies, companies, etc. In computer science, they represent networks of commu￾nication, data organization, computational devices as well as the flow of computa￾tion, and more. In mathematics, Cayley graphs are useful in Group Theory. Graphs carry a natural metric and are therefore useful in Geometry, and though they are “just” one-dimensional complexes, they are useful in certain parts of Topology, e.g. Knot Theory. In statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such systems. The study of these models calls, then, for the comprehension of the significant structural properties of the relevant graphs. But are there nontrivial structural properties which are universally important? Expansion of a graph requires that it is simultaneously sparse and highly connected. Expander graphs were first de- fined by Bassalygo and Pinsker, and their existence first proved by Pinsker in the early ’70s. The property of being an expander seems significant in many of these mathematical, computational and physical contexts. It is not surprising that ex￾panders are useful in the design and analysis of communication networks. What is less obvious is that expanders have surprising utility in other computational settings such as in the theory of error correcting codes and the theory of pseudorandom￾ness. In mathematics, we will encounter e.g. their role in the study of metric embeddings, and in particular in work around the Baum-Connes Conjecture. Ex￾pansion is closely related to the convergence rates of Markov Chains, and so they play a key role in the study of Monte-Carlo algorithms in statistical mechanics and in a host of practical computational applications. The list of such interesting and fruitful connections goes on and on with so many applications we will not even Received by the editors April 28, 2006, and, in revised form, May 10, 2006. 2000 Mathematics Subject Classification. Primary 01-01, 68-01, 05-01, 68Q01, 94-01; Sec￾ondary 68Q15, 68Q17, 94B05, 05C25, 05C35, 05C40, 05C50, 05C80, 05C90, 60J10, 35J99, 20F05, 20F69, 20C99. Work supported in part by grants from the Israel Science Foundation and the Israel-U.S. Binational Fund.
c 2006 S. Hoory, N. Linial, and A. Wigderson 439