440 SHLOMO HOORY.NATHAN LINIAL.AND AVI WIGDERSON be able to mention.This universality of expanders is becoming more evident as more connections are discovered.It transpires that expansion is a fundamental mathematical concept,well deserving to be thoroughly investigated on its own. In hindsight,one reason that expanders are so ubiquitous is that their very defini- tion can be given in at least three languages:combinatorial/geometric,probabilistic and algebraic.Combinatorially,expanders are graphs which are highly connected; to disconnect a large part of the graph,one has to sever many edges.Equivalently, using the geometric notion of isoperimetry,every set of vertices has a (relatively) very large boundary.From the probabilistic viewpoint,one considers the natural random walk on a graph,in which we have a token on a vertex,that moves at every step to a random neighboring vertex,chosen uniformly and independently. Expanders are graphs for which this process converges to its limiting distribution as rapidly as possible.Algebraically,one can consider the Laplace operator on the graph and its spectrum.From this perspective,expanders are graphs in which the first positive eigenvalue(of their Laplace operator)is bounded away from zero. The study of expanders leads in different directions.There are structural prob- lems:what are the best bounds on the various expansion parameters,and how do they relate to each other and to other graph invariants?There are problems concerning explicit constructions:how to efficiently generate expanders with given parameters.These are extremely important for applications.There are algorith- mic problems-given a graph,test if it is an expander with given parameters. Finally,there is the problem of understanding the relation of expansion with other mathematical notions,and the application of expanders to practical and theoretical problems. In the past four decades,a great amount of research has been done on these topics,resulting in a wide-ranging body of knowledge.In this survey,we could not hope to cover even a fraction of it.We have tried to make the presentation as broad as possible,touching on the various research directions mentioned above. Even what we do cover is of course incomplete,and we try to give the relevant references for more comprehensive coverage.We have also tried to mention in each section related research which we are not covering at all and to reference some of this as well. The selection of material naturally reflects our interests and biases.It is rather diverse and can be read in different orders,according to the reader's taste and interests. General background material on the computer science side includes the books on Computational Complexity (specifically,complexity classes)Pap94,Sip97],on Algorithms [CLRSO1]and on Randomized Algorithms MR95],and the survey on the P versus NP problem Wig06. This article evolved from lecture notes for a course on expanders taught at the Hebrew University,Israel,in 2003 by Nati Linial and Avi Wigderson.We are greatly indebted to the scribes of the course notes:Ran Gilad-Bachrach,Danny Harnik. Boaz Barak,Udi Wieder,Eran Ofek,Erez Waisbard,Yael Vinner-Dekel,Yishai Beeri,David Statter,Eyal Bigman,Tamir Hazan,Elon Portugaly,Ariel Elbaz, Yuval Filmus,Michal Igell,Eyal Rozenman,Danny Gutfreund,and Yonatan Bilu. Also,we acknowledge that the proof that Margulis construction is an expander is taken (with slight changes)from course notes of Ravi Boppana,with Mukesh Dalal as scribe.440 SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON be able to mention. This universality of expanders is becoming more evident as more connections are discovered. It transpires that expansion is a fundamental mathematical concept, well deserving to be thoroughly investigated on its own. In hindsight, one reason that expanders are so ubiquitous is that their very defini￾tion can be given in at least three languages: combinatorial/geometric, probabilistic and algebraic. Combinatorially, expanders are graphs which are highly connected; to disconnect a large part of the graph, one has to sever many edges. Equivalently, using the geometric notion of isoperimetry, every set of vertices has a (relatively) very large boundary. From the probabilistic viewpoint, one considers the natural random walk on a graph, in which we have a token on a vertex, that moves at every step to a random neighboring vertex, chosen uniformly and independently. Expanders are graphs for which this process converges to its limiting distribution as rapidly as possible. Algebraically, one can consider the Laplace operator on the graph and its spectrum. From this perspective, expanders are graphs in which the first positive eigenvalue (of their Laplace operator) is bounded away from zero. The study of expanders leads in different directions. There are structural prob￾lems: what are the best bounds on the various expansion parameters, and how do they relate to each other and to other graph invariants? There are problems concerning explicit constructions: how to efficiently generate expanders with given parameters. These are extremely important for applications. There are algorith￾mic problems - given a graph, test if it is an expander with given parameters. Finally, there is the problem of understanding the relation of expansion with other mathematical notions, and the application of expanders to practical and theoretical problems. In the past four decades, a great amount of research has been done on these topics, resulting in a wide-ranging body of knowledge. In this survey, we could not hope to cover even a fraction of it. We have tried to make the presentation as broad as possible, touching on the various research directions mentioned above. Even what we do cover is of course incomplete, and we try to give the relevant references for more comprehensive coverage. We have also tried to mention in each section related research which we are not covering at all and to reference some of this as well. The selection of material naturally reflects our interests and biases. It is rather diverse and can be read in different orders, according to the reader’s taste and interests. General background material on the computer science side includes the books on Computational Complexity (specifically, complexity classes) [Pap94, Sip97], on Algorithms [CLRS01] and on Randomized Algorithms [MR95], and the survey on the P versus NP problem [Wig06]. This article evolved from lecture notes for a course on expanders taught at the Hebrew University, Israel, in 2003 by Nati Linial and Avi Wigderson. We are greatly indebted to the scribes of the course notes: Ran Gilad-Bachrach, Danny Harnik, Boaz Barak, Udi Wieder, Eran Ofek, Erez Waisbard, Yael Vinner-Dekel, Yishai Beeri, David Statter, Eyal Bigman, Tamir Hazan, Elon Portugaly, Ariel Elbaz, Yuval Filmus, Michal Igell, Eyal Rozenman, Danny Gutfreund, and Yonatan Bilu. Also, we acknowledge that the proof that Margulis construction is an expander is taken (with slight changes) from course notes of Ravi Boppana, with Mukesh Dalal as scribe