Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



Expander graphs in pure and applied mathematics

Author: Alexander Lubotzky
Journal: Bull. Amer. Math. Soc. 49 (2012), 113-162
MSC (2010): Primary 01-02, 05C99
Published electronically: November 2, 2011
MathSciNet review: 2869010
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Expander graphs are highly connected sparse finite graphs. They play an important role in computer science as basic building blocks for network constructions, error correcting codes, algorithms, and more. In recent years they have started to play an increasing role also in pure mathematics: number theory, group theory, geometry, and more. This expository article describes their constructions and various applications in pure and applied mathematics.

References [Enhancements On Off] (What's this?)

  • [AJN] M. Abért, A. Jaikin-Zapirain and N, Nikolov, The rank gradient from a combinatorial viewpoint, Groups Geom. Dyn. 5 (2011) 213-230. MR 2782170
  • [AN] M. Abért and N. Nikolov, Rank gradient, cost of groups and the rank versus Heegaard genus problem, J. Euro. Math. Soc., to appear. arXiv:math/0701361
  • [AC] N. Alon and Fan R.K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics 72 (1988), 15-19. MR 0975519 (90f:05080)
  • [ALW] N. Alon, A. Lubotzky and A, Wigderson, Semi-direct product in groups and zig-zag product in graphs: connections and applications (extended abstract), 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), 630637, IEEE Computer Soc., Los Alamitos, CA, 2001. MR 1948752
  • [BHKLS] L. Babai, G. Hetyei, W.M. Kantor, A. Lubotzky, and A. Seress, On the diameter of finite groups, 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), 857-865, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990. MR 1150735
  • [BKL] L. Babai, W.M. Kantor and A. Lubotzky, Small-diameter Cayley graphs for finite simple groups, European J. Combin. 10 (1989), no. 6, 507-522. MR 1022771 (91a:20038)
  • [BNP] L. Babai, N. Nikolov and L. Pyber, Product growth and mixing in finite groups, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 248-257, ACM, New York, 2008. MR 2485310
  • [Ba] L. Bartholdi, On amenability of group algebras. I, Israel J. Math. 168 (2008), 153-165. MR 2448055 (2010a:43001)
  • [BMNVW] F. Bassino, A. Martino, C. Nicaud, E. Ventura and P. Weil, Statistical properties of subgroups of free groups, arXiv:1001.4472
  • [Be] M.B. Bekka, On the full $ C^*$-algebras of arithmetic groups and the congruence subgroup problem, Forum Math. 11 (1999), no. 6, 705-715. MR 1725593 (2001f:22016)
  • [BeSz] E.J. Benveniste and S.J. Szarek, Property $ T$, property $ \tau $ and irreducibility of matrices, preprint.
  • [B1] J. Bourgain, Expanders and dimensional expansion, C. R. Math. Acad. Sci. Paris 347 (2009), no. 7-8, 357-362. MR 2537230 (2010k:11012)
  • [B2] J. Bourgain, New developments in combinatorial number theory and applications, European Congress of Mathematics, 233-251, Eur. Math. Soc., Zurich, 2010. MR 2648328 (2011d:11017)
  • [BF] J. Bourgain and E. Fuchs, A proof of the positive density conjecture for integer Apollonian circle packings, J. Amer. Math. Soc. 24 (2011), 945-967. arXiv:1001.3894 MR 2813334
  • [BFLM] J. Bourgain, A. Furman, E. Lindenstrauss and S. Mozes, Invariant measures and stiffness for non-abelian groups of toral automorphisms, C. R. Math. Acad. Sci. Paris 344 (2007), no. 12, 737-742. MR 2340439 (2008g:37005)
  • [BG1] J. Bourgain and A. Gamburd, Uniform expansion bounds for Cayley graphs of $ {\rm\mathrm {SL}}_2(\mathbb{F}_p)$, Ann. of Math. (2) 167 (2008), no. 2, 625-642. MR 2415383 (2010b:20070)
  • [BG2] J. Bourgain and A. Gamburd, On the spectral gap for finitely-generated subgroups of $ \rm SU(2)$, Invent. Math. 171 (2008), no. 1, 83-121. MR 2358056 (2009g:22018)
  • [BG3] J. Bourgain and A. Gamburd, Expansion and random walks in $ {\rm\mathrm {SL}}_d(\mathbb{Z}/p^n\mathbb{Z})$. I, J. Eur. Math. Soc. (JEMS) 10 (2008), no. 4, 987-1011. MR 2443926 (2010a:05093)
  • [BG4] J. Bourgain and A. Gamburd, Expansion and random walks in $ {\rm\mathrm {SL}}_d(\mathbb{Z}/p^n\mathbb{Z})$. II, with an appendix by J. Bourgain, J. Eur. Math. Soc. (JEMS) 11 (2009), no. 5, 1057-1103. MR 2538500 (2011a:60021)
  • [BGS1] J. Bourgain, A. Gamburd and P. Sarnak, Sieving and expanders, C. R. Math. Acad. Sci. Paris 343 (2006), no. 3, 155-159. MR 2246331 (2007b:11139)
  • [BGS2] J. Bourgain, A. Gamburd and P. Sarnak, Affine linear sieve, expanders, and sum-product, Invent. Math. 179 (2010), no. 3, 559-644. MR 2587341 (2011d:11018)
  • [BGS3] J. Bourgain, A. Gamburd and P. Sarnak, Generalization of Selberg's $ 3/16$ Theorem and Affine Sieve, arXiv:0912.5021
  • [BKT] J. Bourgain, N. Katz and T. Tao, A sum-product estimate in finite fields, and applications, Geom. Funct. Anal. 14 (2004), no. 1, 27-57. MR 2053599 (2005d:11028)
  • [BK] J. Bourgain and A. Kontorovich, On representations of integers in thin subgroups of $ \mathrm {SL}_2\mathbb{Z}$, Geom. Funct. Anal. (GAFA) 20 (2010), 1144-1174. MR 2746949
  • [BV] J. Bourgain and P.P. Varju, Expansion in $ \mathrm {SL}_d(Z/qZ)$, $ q$ arbitrary, arXiv:1006.3365
  • [BCLM] E. Breuillard, Y. De Cornulier, A. Lubotzky and C. Meiri, Conjugacy growth of linear groups. arXiv:1106.4773
  • [BGa] E. Breuillard and A. Gamburd, Strong uniform expansion in $ \mathrm {SL}(2,p)$, Geom. Funct. Anal. (GAFA) 20 (2010), 1201-1209. MR 2746951
  • [BGT1] E. Breuillard, B. Green and T. Tao, Linear Approximate Groups, Electron. Res. Announc. Math. Sci. 17 (2010), 57-67. MR 2718104 (2011g:11018)
  • [BGT2] E. Breuillard, B. Green and T. Tao, Approximate subgroups of linear groups, arXiv:1005.1881
  • [BGT3] E. Breuillard, B. Green and T. Tao, Suzuki groups as expanders, Groups Geom. Dyn. 5 (2011), 281-299. MR 2782174
  • [BGGT1] E. Breuillard, B. Green, R. Guralnick and T. Tao, Strongly dense free subgroups of semisimple algebraic groups, arXiv:1010.4259
  • [BGGT2] E. Breuillard, B. J. Green, R. Guralnick and T. C. Tao, Expansion in finite simple groups of Lie type, in preparation.
  • [Bue] M. R. Buettgens, Property $ \tau $ and von Neumann algebras, Thesis, State University of New York at Buffalo, 2009. MR2712779
  • [BLMS] Y. Bugeaud, F. Luca, M. Mignotte and S. Siksek, On Fibonacci numbers with few prime divisors, Proc. Japan Acad. Ser. A Math. Sci. 81 (2005), no. 2, 17-20. MR 2126070 (2005k:11020)
  • [BS] M. Burger and P. Sarnak, Ramanujan duals. II, Invent. Math. 106 (1991), no. 1, 1-11. MR 1123369 (92m:22005)
  • [Bu] Peter Buser, Geometry and spectra of compact Riemann surfaces, Progress in Mathematics, 106. Birkhäuser Boston, Inc., Boston, MA, 1992. xiv+454 pp. MR 1183224 (93g:58149)
  • [CLMNO] F. Celler, C.R. Leedham-Green, S.H. Murray, A.C. Niemeyer and E.A. O'Brien, Generating random elements of a finite group, Comm. Algebra 23 (1995), no. 13, 4931-4948. MR 1356111 (96h:20115)
  • [Ch] J.R. Chen, On the representation of a larger even integer as the sum of a prime and the product of at most two primes, Sci. Sinica 16 (1973), 157-176. MR 0434997 (55:7959)
  • [Cl] L. Clozel, Démonstration de la conjecture $ \tau $, Invent. Math. 151 (2003), no. 2, 297-328. MR 1953260 (2004f:11049)
  • [DSV] G. Davidoff, P. Sarnak and A. Valette, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, 55. Cambridge University Press, Cambridge, 2003. x+144 pp. MR 1989434 (2004f:11001)
  • [DSC] P. Diaconis and L. Saloff-Coste, Walks on generating sets of groups, Invent. Math. 134 (1998), no. 2, 251-299. MR 1650316 (2000e:60013)
  • [Di] O. Dinai, Growth in $ SL_2$ over finite fields, J. Group Theory, 14 (2011) 273-297. MR 2788087
  • [D] J.D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199-205. MR 0251758 (40:4985)
  • [DT] N.M. Dunfield and W.P. Thurston, Finite covers of random $ 3$-manifolds, Invent. Math. 166 (2006), no. 3, 457-521. MR 2257389 (2007f:57039)
  • [DS] Z. Dvir and A. Shpilka, Towards dimension expanders over finite fields, Twenty-Third Annual IEEE Conference on Computational Complexity, 304-310, IEEE Computer Soc., Los Alamitos, CA, 2008. MR 2500345 (2010f:68069)
  • [E] G. Elek, The amenability of affine algebras, J. Algebra 264 (2003), no. 2, 469-478. MR 1981416 (2004d:16043)
  • [EHK] J. Ellenberg, C. Hall and E. Kowalski, Expander graphs, gonality and variation of Galois representations, arXiv:1008.3675
  • [EMV] J. S. Ellenberg, P. Michel and A. Venkatesh, Linnik's ergodic method and the distribution of integer points on spheres, arXiv:1001.0897
  • [Er] M. Ershov, Golod-Shafarevich groups with property $ (T)$ and Kac-Moody groups, Duke Math. J. 145 (2008), no. 2, 309-339. MR 2449949 (2009i:20060)
  • [EJ] M. Ershov and A. Jaikin-Zapirain, Property $ (T)$ for noncommutative universal lattices, Invent. Math. 179 (2010), no. 2, 303-347. MR 2570119 (2011e:22010)
  • [FGLNP] J. Fox, M. Gromov, V. Lafforgue, A. Naor and J. Pach, Overlap properties of geometric expanders, arXiv:1005.1392
  • [FI] J. Friedlander and H. Iwaniec, Opera de cribro, American Mathematical Society Colloquium Publications, 57. American Mathematical Society, Providence, RI, 2010. xx+527 pp. MR 2647984 (2011d:11227)
  • [Fr] J. Friedman, A proof of Alon's second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100 pp. MR 2437174 (2010e:05181)
  • [Fu] E. Fuchs, Ph.D. Thesis, Princeton University.
  • [FS] E. Fuchs and K. Sanden, Some experiments with integral Apollonian circle packings, arXiv:1001.1406
  • [Gab1] D. Gaboriau, Coût des relations d'équivalence et des groupes, Invent. Math. 139 (2000), no. 1, 41-98. MR 1728876 (2001f:28030)
  • [Gab2] D. Gaboriau, What is Cost? Notices Amer. Math. Soc. 57 (2010), 1295-1296. MR 2761803
  • [Ga1] A. Gamburd, On the spectral gap for infinite index ``congruence'' subgroups of $ {\rm\mathrm {SL}}_2(\bold Z)$, Israel J. Math. 127 (2002), 157-200. MR 1900698 (2003b:11050)
  • [Ga2] A. Gamburd, Expander graphs, random matrices and quantum chaos, Random walks and geometry, 109-140, Walter de Gruyter GmbH & Co. KG, Berlin, 2004. MR 2087781 (2005k:81087)
  • [GHSSV] A. Gamburd, S. Hoory, M. Shahshahani. A. Shalev and B. Virg, On the girth of random Cayley graphs, Random Structures Algorithms 35 (2009), no. 1, 100-117. MR 2532876 (2010i:05310)
  • [GJS] A. Gamburd, D. Jakobson and P. Sarnak, Spectra of elements in the group ring of $ {\rm SU}(2)$, J. Eur. Math. Soc. (JEMS) 1 (1999), no. 1, 51-85. MR 1677685 (2000e:11102)
  • [GH] N. Gill and H.A. Helfgott, Growth of small generating sets in $ \mathrm {SL}_n(Z/pZ)$, arXiv:1002.1605
  • [Gl] G. Glauberman, Factorizations in local subgroups of finite groups, Regional Conference Series in Mathematics, No. 33. American Mathematical Society, Providence, RI, 1977. ix+74 pp. MR 0470072 (57:9839)
  • [Go] W.T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363-387. MR 2410393 (2009f:20105)
  • [GLMWY] R.L. Graham, J.C. Lagarias, C.L. Mallows, L. Colin, A.R. Wilks and C.H. Yan, Apollonian circle packings: number theory, J. Number Theory 100 (2003), no. 1, 1-45. MR 1971245 (2004d:11055)
  • [Gr] B. Green, Approximate groups and their applications: work of Bourgain, Gamburd, Helfgott and Sarnak, arXiv:0911.3354
  • [GT1] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481-547. MR 2415379 (2009e:11181)
  • [GT2] B. Green and T. Tao, Linear equations in primes, Ann. of Math. (2) 171 (2010), no. 3, 1753-1850. MR 2680398 (2011j:11177)
  • [GTZ] B. Green, T. Tao and T. Ziegler, An inverse theorem for the Gowers $ U^{s+1}[N]$-norm. arXiv:1009.3998
  • [Gro1] M. Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003), no. 1, 73-146. MR 1978492 (2004j:20088a)
  • [Gro2] M. Gromov, Singularities, expanders and topology of maps. I. Homology versus volume in the spaces of cycles, Geom. Funct. Anal. 19 (2009), no. 3, 743-841. MR 2563769
  • [Gro3] M. Gromov, Singularities, expanders and topology of maps. II. From combinatorics to topology via algebraic isoperimetry, Geom. Funct. Anal. 20 (2010), 416-526. MR 2671284
  • [GrGu] M. Gromov and L. Guth, Generalizations of the Kolmogorov-Barzdin embedding estimates, arXiv:1103.3423
  • [GL] F. Grunewald and A. Lubotzky, Linear representations of the automorphism group of a free group, Geom. Funct. Anal. 18 (2009), no. 5, 1564-1608. MR 2481737 (2010i:20039)
  • [HL] G.H. Hardy and J.E. Littlewood, Some problems of `Partitio numerorum'; III: On the expression of a number as a sum of primes, Acta Math. 44 (1923), no. 1, 1-70. MR 1555183
  • [H1] H.A. Helfgott, Growth and generation in $ {\rm\mathrm {SL}}_2(\mathbb{Z}/p\mathbb{Z})$, Ann. of Math. (2) 167 (2008), no. 2, 601-623. MR 2415382 (2009i:20094)
  • [H2] H.A. Helfgott, Growth in $ {\rm\mathrm {SL}}_3(\mathbb{Z}/p\mathbb{Z})$, J. Eur. Math. Soc. 13 (2011), 761-851. MR 2781932
  • [HLS] N. Higson, V. Lafforgue and G. Skandalis, Counterexamples to the Baum-Connes conjecture, Geom. Funct. Anal. 12 (2002), no. 2, 330-354. MR 1911663 (2003g:19007)
  • [HLW] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439-561. MR 2247919 (2007h:68055)
  • [HKLS] E. Hrushovski, P.H. Kropholler, A. Lubotzky and A. Shalev, Powers in finitely generated groups, Trans. Amer. Math. Soc. 348 (1996), no. 1, 291-304. MR 1316851 (96f:20061)
  • [IK] H. Iwaniec and E. Kowalski, Analytic Number Theory, American Mathematical Society Colloquium Publications, 53. American Mathematical Society, Providence, RI, 2004. xii+615 pp. MR 2061214 (2005h:11005)
  • [JKZ] F. Jouve, E. Kowalski and D. Zywina, Splitting fields of characteristic polynomials of random elements in arithmetic groups, Israel J. of Math., to appear. arXiv:1008.3662
  • [KL] W.M. Kantor and A. Lubotzky, The probability of generating a finite classical group, Geom. Dedicata 36 (1990), no. 1, 67-87. MR 1065213 (91j:20041)
  • [KLS] W. M. Kantor, A. Lubotzky and A. Shalev, Invariable generation and the Chebotarev invariant of a finite group, J. of Algebra, 348 (2011) 302-314.
  • [KMSS1] I. Kapovich, A. Miasnikov, P. Schupp and V. Shpilrain, Generic-case complexity, decision problems in group theory, and random walks, J. Algebra 264 (2003), no. 2, 665-694. MR 1981427 (2005m:20080)
  • [KMSS2] I. Kapovich, A. Miasnikov, P. Schupp and V. Shpilrain, Average-case complexity and decision problems in group theory, Adv. Math. 190 (2005), no. 2, 343-359. MR 2102661 (2005i:20053)
  • [KS1] I. Kapovich and P. Schupp, On group-theoretic models of randomness and genericity, Groups Geom. Dyn. 2 (2008), no. 3, 383-404. MR 2415305 (2009k:20102)
  • [K1] M. Kassabov, Universal lattices and unbounded rank expanders, Invent. Math. 170 (2007), no. 2, 297-326. MR 2342638 (2009b:20079)
  • [K2] M. Kassabov, Symmetric groups and expander graphs, Invent. Math. 170 (2007), no. 2, 327-354. MR 2342639 (2008g:20009)
  • [KLN] M. Kassabov, A. Lubotzky and N. Nikolov, Finite simple groups as expanders, Proc. Natl. Acad. Sci. USA 103 (2006), no. 16, 6116-6119. MR 2221038 (2007d:20025)
  • [KN] M. Kassabov and N. Nikolov, Universal lattices and property tau, Invent. Math. 165 (2006), no. 1, 209-224. MR 2221141 (2007c:19002)
  • [KaL] T. Kaufman and A. Lubotzky, Edge transitive Ramanujan graphs and highly symmetric LDPC good codes, arXiv:1108.2960.
  • [KaW] T. Kaufman and A. Wigderson, Symmetric LDPC and local Testing, Innovations in Computer Science, 406-421, 2010.
  • [Ka] D.A. Kazhdan, On the connection of the dual space of a group with the structure of its closed subgroups, (Russian) Funkcional. Anal. i Priložen. 1 (1967), 71-74. MR 0209390 (35:288)
  • [Ki] H.H. Kim, Functoriality for the exterior square of $ {\rm GL}_4$ and the symmetric fourth of $ {\rm GL}_2$, with appendix 1 by Dinakar Ramakrishnan and appendix 2 by Kim and Peter Sarnak. J. Amer. Math. Soc. 16 (2003), no. 1, 139-183. MR 1937203 (2003k:11083)
  • [KB] A. N. Kolmogorov and Y.M. Barzdin, On the realization of nets in $ 3$-dimensional space, Probl. Cybernet, 8, 261-268, 1967. See also Selected Works of A.N. Kolmogorov, Vol. 3, pp. 194-202 (and a remark on page 245), Kluwer Academic Publishers, 1993. MR 1228446 (94c:01040)
  • [KO1] A. Kontorovich and H. Oh, Apollonian circle packings and closed horospheres on hyperbolic $ 3$-manifolds, J. Amer. Math. Soc. 24 (2011), 603-648. arXiv:0811.2236 MR 2784325
  • [KO2] A. Kontorovich and H. Oh, Almost prime Pythagorean triples in thin orbits, arXiv:1001.0370
  • [Ko1] E. Kowalski, The large sieve and its applications, Arithmetic geometry, random walks and discrete groups. Cambridge Tracts in Mathematics, 175. Cambridge University Press, Cambridge, 2008. xxii+293 pp. MR 2426239 (2009f:11123)
  • [Ko2] E. Kowalski, Sieve in expansion, Seminar Bourbaki Exp. no. 1028, November 2010. arXiv:1012:2793v1 MR 2643980
  • [La1] M. Lackenby, Expanders, rank and graphs of groups, Israel J. Math. 146 (2005), 357-370. MR 2151608 (2006c:20068)
  • [La2] M. Lackenby, A characterisation of large finitely presented groups, J. Algebra 287 (2005), no. 2, 458-473. MR 2134155 (2006a:20048)
  • [La3] M. Lackenby, Heegaard splittings, the virtually Haken conjecture and property $ (\tau )$, Invent. Math. 164 (2006), no. 2, 317-359. MR 2218779 (2007c:57030)
  • [La4] M. Lackenby, Large groups, property $ (\tau )$ and the homology growth of subgroups, Math. Proc. Cambridge Philos. Soc. 146 (2009), no. 3, 625-648. MR 2496348 (2010g:20091)
  • [LaLR1] M. Lackenby, D.D. Long and A.W. Reid, LERF and the Lubotzky-Sarnak conjecture, Geom. Topol. 12 (2008), no. 4, 2047-2056. MR 2431015 (2009j:57017)
  • [LaLR2] M. Lackenby, D.D. Long and A.W. Reid, Covering spaces of arithmetic $ 3$-orbifolds, Int. Math. Res. Not. IMRN 2008, no. 12, Art. ID rnn036, 38 pp. MR 2426753 (2009c:57031)
  • [Le] G. Levitt, On the cost of generating an equivalence relation, Ergodic Theory Dynam. Systems, 15(6) (1995), 1173-1181. MR 1366313 (96i:58091)
  • [LiSh] M.W. Liebeck and A. Shalev, The probability of generating a finite simple group, Geom. Dedicata 56 (1995), no. 1, 103-113. MR 1338320 (96h:20116)
  • [Lit] T. Li, Rank and genus of $ 3$-manifolds. arXiv:1106.6302v1
  • [Li] N. Linial, Finite metric-spaces: combinatorics, geometry and algorithms, Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), 573-586, Higher Ed. Press, Beijing, 2002. MR 1957562 (2003k:05045)
  • [LLR] D.D. Long, A. Lubotzky and A.W. Reid, Heegaard genus and property $ \tau $ for hyperbolic $ 3$-manifolds, J. Topol. 1 (2008), no. 1, 152-158. MR 2365655 (2008j:57036)
  • [Lo] E. Looijenga, Prym representations of mapping class groups, Geom. Dedicata 64 (1997), no. 1, 69-83. MR 1432535 (98m:57002)
  • [L1] A. Lubotzky, Discrete groups, expanding graphs and invariant measures, with an appendix by Jonathan D. Rogawski. Reprint of the 1994 edition. Modern Birkhäuser Classics. Birkhäuser Verlag, Basel, 2010. iii+192 pp. MR 2569682 (2010i:22011)
  • [L2] A. Lubotzky, Cayley graphs: eigenvalues, expanders and random walks, Surveys in Combinatorics, 1995 (Stirling), 155-189, London Math. Soc. Lecture Note Ser., 218, Cambridge Univ. Press, Cambridge, 1995. MR 1358635 (96k:05081)
  • [L3] A. Lubotzky, Eigenvalues of the Laplacian, the first Betti number and the congruence subgroup problem, Ann. of Math. (2) 144 (1996), no. 2, 441-452. MR 1418904 (98h:22013)
  • [L4] A. Lubotzky, Free quotients and the first Betti number of some hyperbolic manifolds, Transform. Groups 1 (1996), no. 1-2, 71-82. MR 1390750 (97d:57016)
  • [L5] A. Lubotzky, What is$ \dots $property $ (\tau )$, Notices Amer. Math. Soc. 52 (2005), no. 6, 626-627. MR 2147485
  • [L6] A. Lubotzky, Finite simple groups of Lie type as expanders, J. Eur. Math. Soc. 13 (2011), 1331-1341.
  • [LM1] A. Lubotzky and C. Meiri, Sieve methods in group theory: I. powers in linear groups. Geom. Dedicata, to appear.arXiv:1107.3666
  • [LM2] A. Lubotzky and C. Meiri, Sieve methods in group theory: II. The mapping class group. arXiv:1104:2450
  • [LM3] A. Lubotzky and C. Meiri, Sieve methods in group theory: III. $ Aut(F_n)$. arXiv:1104:2450
  • [LP] A. Lubotzky and I. Pak, The product replacement algorithm and Kazhdan's property $ (T)$, J. Amer. Math. Soc. 14 (2001), no. 2, 347-363. MR 1815215 (2003d:60012)
  • [LPS1] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan conjecture and explicit construction of expanders, Proc. STOC. 86 (1986), 240-246.
  • [LPS2] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261-277. MR 963118 (89m:05099)
  • [LPS3] A. Lubotzky, R. Phillips and P. Sarnak, Hecke operators and distributing points on the sphere. I, Frontiers of the mathematical sciences: 1985 (New York, 1985). Comm. Pure Appl. Math. 39 (1986), no. S, suppl., 149-186. MR 861487 (88m:11025a)
  • [LPS4] A. Lubotzky, R. Phillips and P. Sarnak, Hecke operators and distributing points on $ S^2$. II, Comm. Pure Appl. Math. 40 (1987), no. 4, 401-420. MR 890171 (88m:11025b)
  • [LR] A. Lubotzky and L. Rosenzweig, The galois groups of random elements of linear groups, in preparation.
  • [LSV1] A. Lubotzky, B. Samuels and U. Vishne, Ramanujan complexes of type $ \tilde A_d$, Probability in Mathematics. Israel J. Math. 149 (2005), 267-299. MR 2191217 (2006i:11134)
  • [LSV2] A. Lubotzky, B. Samuels and U. Vishne, Explicit constructions of Ramanujan complexes of type $ \tilde A_d$, European J. Combin. 26 (2005), no. 6, 965-993. MR 2143204 (2006g:20043)
  • [LS] A. Lubotzky and D. Segal, Subgroup growth, Progress in Mathematics, 212. Birkhäuser Verlag, Basel, 2003. xxii+453 pp. MR 1978431 (2004k:20055)
  • [LSh] A. Lubotzky and Y. Shalom, Finite representations in the unitary dual and Ramanujan groups, Discrete geometric analysis, 173-189, Contemp. Math., 347, Amer. Math. Soc., Providence, RI, 2004. MR 2077037 (2005e:22011)
  • [LW] A. Lubotzky and B. Weiss, Groups and expanders, Expanding graphs (Princeton, NJ, 1992), 95-109, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 10, Amer. Math. Soc., Providence, RI, 1993. MR 1235570 (95b:05097)
  • [LZ] A. Lubotzky and E. Zelmanov, Dimension expanders, J. Algebra 319 (2008), no. 2, 730-738. MR 2381805 (2008k:05098)
  • [LZi] A. Lubotzky and R.J. Zimmer, Variants of Kazhdan's property for subgroups of semisimple groups, Israel J. Math. 66 (1989), no. 1-3, 289-299. MR 1017168 (90i:22020)
  • [LZu] A. Lubtozky and A. Zuk, On property $ (\tau )$, monograph in preparation.
  • [Ma1] J. Maher, Random walks on the mapping class group, Duke Math. J. 156 (2011), 429-468. MR 2772067
  • [Ma2] J. Maher, Random Heegaard splittings, J.Topology 3 (2010), 997-1025. MR 2746344
  • [MS] J. Malestein and J. Souto, On genericity of pseudo-Anosovs in the Torelli group, arXiv:1102.0601
  • [M1] G.A. Margulis, Explicit constructions of expanders. (Russian) Problemy Peredači Informacii 9 (1973), no. 4, 71-80. English translation: Problems of Information Transmission 9 (1973), no. 4, 325-332 (1975). MR 0484767 (58:4643)
  • [M2] G.A. Margulis, Explicit constructions of graphs without short cycles and low density codes, Combinatorica 2 (1982), no. 1, 71-78. MR 671147 (83j:05053)
  • [M3] G.A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problems of Information Transmission, 24(1):39-46, 1988. MR 939574 (89f:68054)
  • [MVW] C.R. Matthews, L.N. Vaserstein and B. Weisfeiler, Congruence properties of Zariski-dense subgroups. I, Proc. London Math. Soc. (3) 48 (1984), no. 3, 514-532. MR 735226 (85d:20040)
  • [Maz] B. Mazur, It is a story, A lecture given at Diaconis' 60th birthday. Available at williams/diaconis/
  • [MW] R. Meshulam and A. Wigderson, Expanders in group algebras, Combinatorica 24 (2004), no. 4, 659-680. MR 2096820 (2005m:05114)
  • [Mo] M. Morgenstern, Existence and explicit constructions of $ q+1$ regular Ramanujan graphs for every prime power $ q$, J. Combin. Theory Ser. B 62 (1994), 44-62. MR 1290630 (95h:05089)
  • [MR] A.G. Myasnikov and A.N. Rybalov, Generic complexity of undecidable problems, J. Symbolic Logic 73 (2008), no. 2, 656-673. MR 2414470 (2009g:03068)
  • [NS] A. Nevo and P. Sarnak, Prime and almost prime integral points on principal homogeneous spaces, Acta Math. 205 (2010), 361-402. MR 2746350
  • [Ni] N. Nikolov, A product of decomposition for the classical quasisimple groups, J. Group Theory 10 (2007), no. 1, 43-53. MR 2288458 (2007m:20073)
  • [NiPy] N. Nikolov and L. Pyber, Product decompositions of quasirandom groups and a Jordan type theorem, arXiv:math/0703343
  • [No] M.V. Nori, On subgroups of $ {\rm GL}_n({\bf F}_p)$, Invent. Math. 88 (1987), no. 2, 257-275. MR 880952 (88d:20068)
  • [Pi] R. Pink, Strong approximation for Zariski dense subgroups over arbitrary global fields, Comment. Math. Helv. 75 (2000), no. 4, 608-643. MR 1789179 (2001k:20106)
  • [Pin] M.S. Pinsker, On the complexity of a concentrator, 7th International Teletraffic Conference, Stockholm, pages 318/1-318/4, June 1973.
  • [PS1] L. Pyber and E. Szabó, Growth in finite simple groups of Lie type, arXiv:1001.4556
  • [PS2] L. Pyber and E. Szabó, Growth in finite simple groups of Lie type of bounded rank, arXiv:1005.1858
  • [RVW] O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math. (2) 155 (2002), no. 1, 157-187. MR 1888797 (2003c:05145)
  • [Ri1] I. Rivin, Walks on groups, counting reducible matrices, polynomials, and surface and free group automorphisms, Duke Math. J. 142 (2008), no. 2, 353-379. MR 2401624 (2009m:20077)
  • [Ri2] I. Rivin, Zarisky density and genericity, Int. Math. Res. Not. IMRN 19 (2010), 3649-3657. MR 2725508
  • [RSW] E. Rozenman, A. Shalev and A. Wigderson, Iterative construction of Cayley expander graphs, Theory Comput. 2 (2006), 91-120. MR 2322872 (2009b:05133)
  • [SGS] A. Salehi Golsefidy and P. Sarnak, Affine linear sieve, arXiv:1109.6432.
  • [SGV] A. Salehi Golsefidy and P. Varju, Expansion in perfect groups, arXiv:1108.4900.
  • [S1] P. Sarnak, Some applications of modular forms, Cambridge Tracts in Mathematics, 99. Cambridge University Press, Cambridge, 1990. x+111 pp. MR 1102679 (92k:11045)
  • [S2] P. Sarnak, Selberg's eigenvalue conjecture, Notices Amer. Math. Soc. 42 (1995), no. 11, 1272-1277. MR 1355461 (97c:11059)
  • [S3] P. Sarnak, What is $ \dots $ an expander? Notices Amer. Math. Soc. 51 (2004), no. 7, 762-763. MR 2072849
  • [S4] P. Sarnak, Equidistribution and primes, Géométrie differentielle, physique mathématiques, mathématiques et société. II. Astérisque No. 322 (2008), 225-240. MR 2521658 (2010k:11146)
  • [S5] P. Sarnak, Letter to Lagarias on integral Apollonian packings. Available at
  • [S6] P. Sarnak, Equidistribution and Primes, (2007) PIMS Lecture. Available at
  • [S7] P. Sarnak, Primes and orbits, MAA Garden State lecture. Available at
  • [S8] P. Sarnak, Integral Apollonian Packings - MAA Lecture January 2009. Available at http://www.math.princeton
  • [SS] A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, (French) Acta Arith. 4 (1958), 185-208; erratum 5 (1958) 259. MR 0106202 (21:4936)
  • [SiSp] M. Sipser and D.A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42 (1996), 1710-1722. MR 1465731 (98d:94031)
  • [Sel] A. Selberg, On the estimation of Fourier coefficients of modular forms, 1965 Proc. Sympos. Pure Math., Vol. VIII, pp. 1-15, Amer. Math. Soc., Providence, RI MR 0182610 (32:93)
  • [Se] J-P. Serre, Le problème des groupes de congruence pour $ \mathrm {SL}_2$, (French) Ann. of Math. (2) 92 (1970) 489-527. MR 0272790 (42:7671)
  • [Sh1] Y. Shalom, Expanding graphs and invariant means, Combinatorica 17 (1997), no. 4, 555-575. MR 1645694 (99h:05057)
  • [Sh2] Y. Shalom, Expander graphs and amenable quotients, Emerging applications of number theory (Minneapolis, MN, 1996), 571-581, IMA Vol. Math. Appl., 109, Springer, New York, 1999. MR 1691549 (2000h:20059)
  • [Sh3] Y. Shalom, Bounded generation and Kazhdan's property $ (T)$, Inst. Hautes Études Sci. Publ. Math. No. 90 (1999), 145-168 (2001). MR 1813225 (2001m:22030)
  • [Sh4] Y. Shalom, The algebraization of Kazhdan's property $ (T)$, International Congress of Mathematicians. Vol. II, 1283-1310, Eur. Math. Soc., Zurich, 2006. MR 2275645 (2008a:22003)
  • [Ta] R. M. Tanner, A recursive approach to low complexity codes, IEEE Transactions on Information Theory 27 (1981), 533-547. MR 650686 (83i:94017)
  • [TV] T. Tao and V. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, 105. Cambridge University Press, Cambridge, 2006. xviii+512 pp. MR 2289012 (2008a:11002)
  • [Ti] J. Tits, Free subgroups in linear groups, J. Algebra 20 (1972) 250-270. MR 0286898 (44:4105)
  • [Va1] A. Valette, An application of Ramanujan graphs to $ C^*$-algebra tensor products, 15th British Combinatorial Conference (Stirling, 1995). Discrete Math. 167/168 (1997), 597-603. MR 1446777 (98d:46066)
  • [Va2] A. Valette, Graphes de Ramanujan et applications, (French) Ramanujan graphs and applications, Séminaire Bourbaki, Vol. 1996/97. Astérisque No. 245 (1997), Exp. No. 829, 4, 247-276. MR 1627114 (99k:11079)
  • [Va3] A. Valette, Introduction to the Baum-Connes conjecture, Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2002. MR 1907596 (2003f:58047)
  • [V] P.O. Varju, Expansion in $ \mathrm {SL}_d(O_K/I)$, $ I$ square-free, arXiv:1001.3664.
  • [W] B. Weisfeiler, Strong approximation for Zariski-dense subgroups of semisimple algebraic groups, Ann. of Math. (2) 120 (1984), no. 2, 271-315. MR 763908 (86m:20053)
  • [Z1] P. Zograf, Small eigenvalues of automorphic Laplacians in spaces of cusp forms, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov (LOMI) 134 (1994), 157-168; translation in J. Math. Sciences 36, No. 1, 106-114. MR 741858 (86a:58116)
  • [Z2] P. Zograf, A spectral proof of Rademacher's conjecture for congruence subgroups of the modular group, J. Reine Angew. Math. 414 (1991), 113-116. MR 1092625 (92d:11041)
  • [Z] A. Zuk, Property (T) and Kazhdan constants for discrete groups, Geom. Funct. Anal. 13 (2003), no. 3, 643-670. MR 1995802 (2004m:20079)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 01-02, 05C99

Retrieve articles in all journals with MSC (2010): 01-02, 05C99

Additional Information

Alexander Lubotzky
Affiliation: Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel

Received by editor(s): May 12, 2011
Received by editor(s) in revised form: June 7, 2011
Published electronically: November 2, 2011
Additional Notes: This paper is based on notes prepared for the Colloquium Lectures at the Joint Annual Meeting of the American Mathematical Society (AMS) and the Mathematical Association of America (MAA), New Orleans, LA, January 6–9, 2011. The author is grateful to the AMS for the opportunity to present this material for a wide audience. He has benefited by responses and remarks which followed his lectures
Dedicated: Dedicated to the memory of Jonathan Rogawski
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society