Bulletin of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

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
Posted: November 2, 2011
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

[AJN] Miklós Abért, Andrei Jaikin-Zapirain, and Nikolay Nikolov, The rank gradient from a combinatorial viewpoint, Groups Geom. Dyn. 5 (2011), no. 2, 213–230. MR 2782170, http://dx.doi.org/10.4171/GGD/124
[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 F. R. K. Chung, Explicit construction of linear sized tolerant networks, Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), 1988, pp. 15–19. MR 975519 (90f:05080), http://dx.doi.org/10.1016/0012-365X(88)90189-6
[ALW] Noga Alon, Alexander Lubotzky, and Avi 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), IEEE Computer Soc., Los Alamitos, CA, 2001, pp. 630–637. MR 1948752
[BHKLS] L. Babai, G. Hetyei, W. M. Kantor, A. Lubotzky, and Á. Seress, On the diameter of finite groups, (St. Louis, MO, 1990) IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, pp. 857–865. MR 1150735, http://dx.doi.org/10.1109/FSCS.1990.89608
[BKL] L. Babai, W. M. Kantor, and A. Lubotsky, Small-diameter Cayley graphs for finite simple groups, European J. Combin. 10 (1989), no. 6, 507–522. MR 1022771 (91a:20038)
[BNP] László Babai, Nikolay Nikolov, and László Pyber, Product growth and mixing in finite groups, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2008, pp. 248–257. MR 2485310
[Ba] Laurent Bartholdi, On amenability of group algebras. I, Israel J. Math. 168 (2008), 153–165. MR 2448055 (2010a:43001), http://dx.doi.org/10.1007/s11856-008-1061-7
[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 𝐶*-algebras of arithmetic groups and the congruence subgroup problem, Forum Math. 11 (1999), no. 6, 705–715. MR 1725593 (2001f:22016), http://dx.doi.org/10.1515/form.1999.021
[BeSz] E.J. Benveniste and S.J. Szarek, Property , property $\tau$ and irreducibility of matrices, preprint.
[B1] Jean Bourgain, Expanders and dimensional expansion, C. R. Math. Acad. Sci. Paris 347 (2009), no. 7-8, 357–362 (English, with English and French summaries). MR 2537230 (2010k:11012), http://dx.doi.org/10.1016/j.crma.2009.02.009
[B2] Jean Bourgain, New developments in combinatorial number theory and applications, European Congress of Mathematics, Eur. Math. Soc., Zürich, 2010, pp. 233–251. MR 2648328 (2011d:11017), http://dx.doi.org/10.4171/077-1/11
[BF] Jean Bourgain and Elena Fuchs, A proof of the positive density conjecture for integer Apollonian circle packings, J. Amer. Math. Soc. 24 (2011), no. 4, 945–967. MR 2813334 (2012d:11072), http://dx.doi.org/10.1090/S0894-0347-2011-00707-8
[BFLM] Jean Bourgain, Alex Furman, Elon Lindenstrauss, and Shahar Mozes, Invariant measures and stiffness for non-abelian groups of toral automorphisms, C. R. Math. Acad. Sci. Paris 344 (2007), no. 12, 737–742 (English, with English and French summaries). MR 2340439 (2008g:37005), http://dx.doi.org/10.1016/j.crma.2007.04.017
[BG1] Jean Bourgain and Alex Gamburd, Uniform expansion bounds for Cayley graphs of 𝑆𝐿₂(𝔽_{𝕡}), Ann. of Math. (2) 167 (2008), no. 2, 625–642. MR 2415383 (2010b:20070), http://dx.doi.org/10.4007/annals.2008.167.625
[BG2] Jean Bourgain and Alex Gamburd, On the spectral gap for finitely-generated subgroups of 𝑆𝑈(2), Invent. Math. 171 (2008), no. 1, 83–121. MR 2358056 (2009g:22018), http://dx.doi.org/10.1007/s00222-007-0072-z
[BG3] Jean Bourgain and Alex Gamburd, Expansion and random walks in 𝑆𝐿_{𝑑}(ℤ/𝕡ⁿℤ). I, J. Eur. Math. Soc. (JEMS) 10 (2008), no. 4, 987–1011. MR 2443926 (2010a:05093), http://dx.doi.org/10.4171/JEMS/137
[BG4] Jean Bourgain and Alex Gamburd, Expansion and random walks in 𝑆𝐿_{𝑑}(ℤ/𝕡ⁿℤ). II, J. Eur. Math. Soc. (JEMS) 11 (2009), no. 5, 1057–1103. With an appendix by Bourgain. MR 2538500 (2011a:60021), http://dx.doi.org/10.4171/JEMS/175
[BGS1] Jean Bourgain, Alex Gamburd, and Peter Sarnak, Sieving and expanders, C. R. Math. Acad. Sci. Paris 343 (2006), no. 3, 155–159 (English, with English and French summaries). MR 2246331 (2007b:11139), http://dx.doi.org/10.1016/j.crma.2006.05.023
[BGS2] Jean Bourgain, Alex Gamburd, and Peter Sarnak, Affine linear sieve, expanders, and sum-product, Invent. Math. 179 (2010), no. 3, 559–644. MR 2587341 (2011d:11018), http://dx.doi.org/10.1007/s00222-009-0225-3
[BGS3] J. Bourgain, A. Gamburd and P. Sarnak, Generalization of Selberg's 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), http://dx.doi.org/10.1007/s00039-004-0451-1
[BK] Jean Bourgain and Alex Kontorovich, On representations of integers in thin subgroups of 𝑆𝐿₂(ℤ), Geom. Funct. Anal. 20 (2010), no. 5, 1144–1174. MR 2746949, http://dx.doi.org/10.1007/s00039-010-0093-4
[BV] J. Bourgain and P.P. Varju, Expansion in $\mathrm {SL}_d(Z/qZ)$ , arbitrary, arXiv:1006.3365
[BCLM] E. Breuillard, Y. De Cornulier, A. Lubotzky and C. Meiri, Conjugacy growth of linear groups. arXiv:1106.4773
[BGa] Emmanuel Breuillard and Alex Gamburd, Strong uniform expansion in 𝑆𝐿(2,𝑝), Geom. Funct. Anal. 20 (2010), no. 5, 1201–1209. MR 2746951 (2011m:20111), http://dx.doi.org/10.1007/s00039-010-0094-3
[BGT1] Emmanuel Breuillard, Ben Green, and Terence Tao, Linear approximate groups, Electron. Res. Announc. Math. Sci. 17 (2010), 57–67. MR 2718104 (2011g:11018), http://dx.doi.org/10.3934/era.2010.17.57
[BGT2] E. Breuillard, B. Green and T. Tao, Approximate subgroups of linear groups, arXiv:1005.1881
[BGT3] Emmanuel Breuillard, Ben Green, and Terence Tao, Suzuki groups as expanders, Groups Geom. Dyn. 5 (2011), no. 2, 281–299. MR 2782174 (2012c:20066), http://dx.doi.org/10.4171/GGD/128
[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] Yann Bugeaud, Florian Luca, Maurice Mignotte, and Samir 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), http://dx.doi.org/10.1007/BF01243900
[Bu] Peter Buser, Geometry and spectra of compact Riemann surfaces, Progress in Mathematics, vol. 106, Birkhäuser Boston Inc., Boston, MA, 1992. MR 1183224 (93g:58149)
[CLMNO] Frank Celler, Charles R. Leedham-Green, Scott H. Murray, Alice 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), http://dx.doi.org/10.1080/00927879508825509
[Ch] Jing Run 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] Laurent Clozel, Démonstration de la conjecture 𝜏, Invent. Math. 151 (2003), no. 2, 297–328 (French). MR 1953260 (2004f:11049), http://dx.doi.org/10.1007/s00222-002-0253-8
[DSV] Giuliana Davidoff, Peter Sarnak, and Alain Valette, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge, 2003. 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), http://dx.doi.org/10.1007/s002220050265
[Di] Oren Dinai, Growth in 𝑆𝐿₂ over finite fields, J. Group Theory 14 (2011), no. 2, 273–297. MR 2788087 (2012c:20134), http://dx.doi.org/10.1515/JGT.2010.056
[D] John D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199–205. MR 0251758 (40 #4985)
[DT] Nathan M. Dunfield and William P. Thurston, Finite covers of random 3-manifolds, Invent. Math. 166 (2006), no. 3, 457–521. MR 2257389 (2007f:57039), http://dx.doi.org/10.1007/s00222-006-0001-6
[DS] Zeev Dvir and Amir Shpilka, Towards dimension expanders over finite fields, Twenty-Third Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2008, pp. 304–310. MR 2500345 (2010f:68069), http://dx.doi.org/10.1109/CCC.2008.19
[E] Gábor Elek, The amenability of affine algebras, J. Algebra 264 (2003), no. 2, 469–478. MR 1981416 (2004d:16043), http://dx.doi.org/10.1016/S0021-8693(03)00163-7
[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] Mikhail Ershov, Golod-Shafarevich groups with property (𝑇) and Kac-Moody groups, Duke Math. J. 145 (2008), no. 2, 309–339. MR 2449949 (2009i:20060), http://dx.doi.org/10.1215/00127094-2008-053
[EJ] Mikhail Ershov and Andrei Jaikin-Zapirain, Property (T) for noncommutative universal lattices, Invent. Math. 179 (2010), no. 2, 303–347. MR 2570119 (2011e:22010), http://dx.doi.org/10.1007/s00222-009-0218-2
[FGLNP] J. Fox, M. Gromov, V. Lafforgue, A. Naor and J. Pach, Overlap properties of geometric expanders, arXiv:1005.1392
[FI] John Friedlander and Henryk Iwaniec, Opera de cribro, American Mathematical Society Colloquium Publications, vol. 57, American Mathematical Society, Providence, RI, 2010. MR 2647984 (2011d:11227)
[Fr] Joel Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100. 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] Damien Gaboriau, Coût des relations d’équivalence et des groupes, Invent. Math. 139 (2000), no. 1, 41–98 (French, with English summary). MR 1728876 (2001f:28030), http://dx.doi.org/10.1007/s002229900019
[Gab2] Damien Gaboriau, What is … cost?, Notices Amer. Math. Soc. 57 (2010), no. 10, 1295–1296. MR 2761803 (2012c:37005)
[Ga1] Alex Gamburd, On the spectral gap for infinite index “congruence” subgroups of 𝑆𝐿₂(𝐙), Israel J. Math. 127 (2002), 157–200. MR 1900698 (2003b:11050), http://dx.doi.org/10.1007/BF02784530
[Ga2] Alex Gamburd, Expander graphs, random matrices and quantum chaos, Random walks and geometry, Walter de Gruyter GmbH & Co. KG, Berlin, 2004, pp. 109–140. MR 2087781 (2005k:81087)
[GHSSV] A. Gamburd, S. Hoory, M. Shahshahani, A. Shalev, and B. Virág, On the girth of random Cayley graphs, Random Structures Algorithms 35 (2009), no. 1, 100–117. MR 2532876 (2010i:05310), http://dx.doi.org/10.1002/rsa.20266
[GJS] Alex Gamburd, Dmitry Jakobson, and Peter Sarnak, Spectra of elements in the group ring of 𝑆𝑈(2), J. Eur. Math. Soc. (JEMS) 1 (1999), no. 1, 51–85. MR 1677685 (2000e:11102), http://dx.doi.org/10.1007/PL00011157
[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, American Mathematical Society, Providence, R.I., 1977. Regional Conference Series in Mathematics, No. 33. MR 0470072 (57 #9839)
[Go] W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363–387. MR 2410393 (2009f:20105), http://dx.doi.org/10.1017/S0963548307008826
[GLMWY] Ronald L. Graham, Jeffrey C. Lagarias, Colin L. Mallows, Allan R. Wilks, and Catherine H. Yan, Apollonian circle packings: number theory, J. Number Theory 100 (2003), no. 1, 1–45. MR 1971245 (2004d:11055), http://dx.doi.org/10.1016/S0022-314X(03)00015-5
[Gr] B. Green, Approximate groups and their applications: work of Bourgain, Gamburd, Helfgott and Sarnak, arXiv:0911.3354
[GT1] Ben Green and Terence Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481–547. MR 2415379 (2009e:11181), http://dx.doi.org/10.4007/annals.2008.167.481
[GT2] Benjamin Green and Terence Tao, Linear equations in primes, Ann. of Math. (2) 171 (2010), no. 3, 1753–1850. MR 2680398 (2011j:11177), http://dx.doi.org/10.4007/annals.2010.171.1753
[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), http://dx.doi.org/10.1007/s000390300002
[Gro2] Mikhail 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 (2012a:58062), http://dx.doi.org/10.1007/s00039-009-0021-7
[Gro3] Mikhail Gromov, Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geom. Funct. Anal. 20 (2010), no. 2, 416–526. MR 2671284 (2012a:58063), http://dx.doi.org/10.1007/s00039-010-0073-8
[GrGu] M. Gromov and L. Guth, Generalizations of the Kolmogorov-Barzdin embedding estimates, arXiv:1103.3423
[GL] Fritz Grunewald and Alexander Lubotzky, Linear representations of the automorphism group of a free group, Geom. Funct. Anal. 18 (2009), no. 5, 1564–1608. MR 2481737 (2010i:20039), http://dx.doi.org/10.1007/s00039-009-0702-2
[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, http://dx.doi.org/10.1007/BF02403921
[H1] H. A. Helfgott, Growth and generation in 𝑆𝐿₂(ℤ/𝕡ℤ), Ann. of Math. (2) 167 (2008), no. 2, 601–623. MR 2415382 (2009i:20094), http://dx.doi.org/10.4007/annals.2008.167.601
[H2] H. A. Helfgott, Growth in 𝑆𝐿₃(ℤ/𝕡ℤ), J. Eur. Math. Soc. (JEMS) 13 (2011), no. 3, 761–851. MR 2781932, http://dx.doi.org/10.4171/JEMS/267
[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), http://dx.doi.org/10.1007/s00039-002-8249-5
[HLW] Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561 (electronic). MR 2247919 (2007h:68055), http://dx.doi.org/10.1090/S0273-0979-06-01126-8
[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), http://dx.doi.org/10.1090/S0002-9947-96-01456-0
[IK] Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. 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] William M. Kantor and Alexander Lubotzky, The probability of generating a finite classical group, Geom. Dedicata 36 (1990), no. 1, 67–87. MR 1065213 (91j:20041), http://dx.doi.org/10.1007/BF00181465
[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] Ilya Kapovich, Alexei Miasnikov, Paul Schupp, and Vladimir Shpilrain, Generic-case complexity, decision problems in group theory, and random walks, J. Algebra 264 (2003), no. 2, 665–694. MR 1981427 (2005m:20080), http://dx.doi.org/10.1016/S0021-8693(03)00167-4
[KMSS2] Ilya Kapovich, Alexei Miasnikov, Paul Schupp, and Vladimir Shpilrain, Average-case complexity and decision problems in group theory, Adv. Math. 190 (2005), no. 2, 343–359. MR 2102661 (2005i:20053), http://dx.doi.org/10.1016/j.aim.2003.02.001
[KS1] Ilya Kapovich and Paul Schupp, On group-theoretic models of randomness and genericity, Groups Geom. Dyn. 2 (2008), no. 3, 383–404. MR 2415305 (2009k:20102), http://dx.doi.org/10.4171/GGD/45
[K1] Martin Kassabov, Universal lattices and unbounded rank expanders, Invent. Math. 170 (2007), no. 2, 297–326. MR 2342638 (2009b:20079), http://dx.doi.org/10.1007/s00222-007-0064-z
[K2] Martin Kassabov, Symmetric groups and expander graphs, Invent. Math. 170 (2007), no. 2, 327–354. MR 2342639 (2008g:20009), http://dx.doi.org/10.1007/s00222-007-0065-y
[KLN] Martin Kassabov, Alexander Lubotzky, and Nikolay Nikolov, Finite simple groups as expanders, Proc. Natl. Acad. Sci. USA 103 (2006), no. 16, 6116–6119 (electronic). MR 2221038 (2007d:20025), http://dx.doi.org/10.1073/pnas.0510337103
[KN] Martin Kassabov and Nikolay Nikolov, Universal lattices and property tau, Invent. Math. 165 (2006), no. 1, 209–224. MR 2221141 (2007c:19002), http://dx.doi.org/10.1007/s00222-005-0498-0
[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. Každan, On the connection of the dual space of a group with the structure of its closed subgroups, Funkcional. Anal. i Priložen. 1 (1967), 71–74 (Russian). MR 0209390 (35 #288)
[Ki] Henry H. Kim, Functoriality for the exterior square of 𝐺𝐿₄ and the symmetric fourth of 𝐺𝐿₂, J. Amer. Math. Soc. 16 (2003), no. 1, 139–183 (electronic). With appendix 1 by Dinakar Ramakrishnan and appendix 2 by Kim and Peter Sarnak. MR 1937203 (2003k:11083), http://dx.doi.org/10.1090/S0894-0347-02-00410-1
[KB] A. N. Kolmogorov, Selected works of A. N. Kolmogorov. Vol. III, Mathematics and its Applications (Soviet Series), vol. 27, Kluwer Academic Publishers Group, Dordrecht, 1993. Information theory and the theory of algorithms; With a biography of Kolmogorov by N. N. Bogolyubov, B. V. Gnedenko and S. L. Sobolev; With commentaries by R. L. Dobrushin, A. Kh. Shen′, V. M. Tikhomirov, Ya. M. Barzdin [Jānis Bārzdinš], Ya. G. Sinaĭ, V. A. Uspenski [V. A. Uspenskiĭ] and A. L. Semyonov; Edited by A. N. Shiryayev [A. N. Shiryaev]; Translated from the 1987 Russian original by A. B. Sossinsky [A. B. Sosinskiĭ]. MR 1228446 (94c:01040)
[KO1] Alex Kontorovich and Hee Oh, Apollonian circle packings and closed horospheres on hyperbolic 3-manifolds, J. Amer. Math. Soc. 24 (2011), no. 3, 603–648. With an appendix by Oh and Nimish Shah. MR 2784325, http://dx.doi.org/10.1090/S0894-0347-2011-00691-7
[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, Cambridge Tracts in Mathematics, vol. 175, Cambridge University Press, Cambridge, 2008. Arithmetic geometry, random walks and discrete groups. MR 2426239 (2009f:11123)
[Ko2] E. Kowalski, Amplification arguments for large sieve inequalities, Arch. Math. (Basel) 94 (2010), no. 5, 443–457. MR 2643980 (2012c:11196), http://dx.doi.org/10.1007/s00013-010-0122-4
[La1] Marc Lackenby, Expanders, rank and graphs of groups, Israel J. Math. 146 (2005), 357–370. MR 2151608 (2006c:20068), http://dx.doi.org/10.1007/BF02773541
[La2] Marc Lackenby, A characterisation of large finitely presented groups, J. Algebra 287 (2005), no. 2, 458–473. MR 2134155 (2006a:20048), http://dx.doi.org/10.1016/j.jalgebra.2005.03.004
[La3] Marc Lackenby, Heegaard splittings, the virtually Haken conjecture and property (𝜏), Invent. Math. 164 (2006), no. 2, 317–359. MR 2218779 (2007c:57030), http://dx.doi.org/10.1007/s00222-005-0480-x
[La4] Marc Lackenby, Large groups, property (𝜏) and the homology growth of subgroups, Math. Proc. Cambridge Philos. Soc. 146 (2009), no. 3, 625–648. MR 2496348 (2010g:20091), http://dx.doi.org/10.1017/S0305004108002089
[LaLR1] Marc Lackenby, Darren D. Long, and Alan W. Reid, LERF and the Lubotzky-Sarnak conjecture, Geom. Topol. 12 (2008), no. 4, 2047–2056. MR 2431015 (2009j:57017), http://dx.doi.org/10.2140/gt.2008.12.2047
[LaLR2] Marc Lackenby, Darren D. Long, and Alan W. Reid, Covering spaces of arithmetic 3-orbifolds, Int. Math. Res. Not. IMRN 12 (2008), Art. ID rnn036, 38. MR 2426753 (2009c:57031), http://dx.doi.org/10.1093/imrn/rnn036
[Le] Gilbert Levitt, On the cost of generating an equivalence relation, Ergodic Theory Dynam. Systems 15 (1995), no. 6, 1173–1181. MR 1366313 (96i:58091), http://dx.doi.org/10.1017/S0143385700009846
[LiSh] Martin W. Liebeck and Aner Shalev, The probability of generating a finite simple group, Geom. Dedicata 56 (1995), no. 1, 103–113. MR 1338320 (96h:20116), http://dx.doi.org/10.1007/BF01263616
[Lit] T. Li, Rank and genus of -manifolds. arXiv:1106.6302v1
[Li] Nathan Linial, Finite metric-spaces—combinatorics, geometry and algorithms, (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 573–586. MR 1957562 (2003k:05045)
[LLR] D. D. Long, A. Lubotzky, and A. W. Reid, Heegaard genus and property 𝜏 for hyperbolic 3-manifolds, J. Topol. 1 (2008), no. 1, 152–158. MR 2365655 (2008j:57036), http://dx.doi.org/10.1112/jtopol/jtm010
[Lo] Eduard Looijenga, Prym representations of mapping class groups, Geom. Dedicata 64 (1997), no. 1, 69–83. MR 1432535 (98m:57002), http://dx.doi.org/10.1023/A:1004909416648
[L1] Alexander Lubotzky, Discrete groups, expanding graphs and invariant measures, Modern Birkhäuser Classics, Birkhäuser Verlag, Basel, 2010. With an appendix by Jonathan D. Rogawski; Reprint of the 1994 edition. MR 2569682 (2010i:22011)
[L2] Alexander Lubotzky, Cayley graphs: eigenvalues, expanders and random walks, Surveys in combinatorics, 1995 (Stirling), London Math. Soc. Lecture Note Ser., vol. 218, Cambridge Univ. Press, Cambridge, 1995, pp. 155–189. MR 1358635 (96k:05081), http://dx.doi.org/10.1017/CBO9780511662096.008
[L3] Alexander 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), http://dx.doi.org/10.2307/2118597
[L4] Alexander 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), http://dx.doi.org/10.1007/BF02587736
[L5] Alex Lubotzky, What is…property (𝜏)?, 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. . arXiv:1104:2450
[LP] Alexander Lubotzky and Igor Pak, The product replacement algorithm and Kazhdan’s property (T), J. Amer. Math. Soc. 14 (2001), no. 2, 347–363 (electronic). MR 1815215 (2003d:60012), http://dx.doi.org/10.1090/S0894-0347-00-00356-8
[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), http://dx.doi.org/10.1007/BF02126799
[LPS3] A. Lubotzky, R. Phillips, and P. Sarnak, Hecke operators and distributing points on the sphere. I, Comm. Pure Appl. Math. 39 (1986), no. S, suppl., S149–S186. Frontiers of the mathematical sciences: 1985 (New York, 1985). MR 861487 (88m:11025a), http://dx.doi.org/10.1002/cpa.3160390710
[LPS4] A. Lubotzky, R. Phillips, and P. Sarnak, Hecke operators and distributing points on 𝑆². II, Comm. Pure Appl. Math. 40 (1987), no. 4, 401–420. MR 890171 (88m:11025b), http://dx.doi.org/10.1002/cpa.3160400402
[LR] A. Lubotzky and L. Rosenzweig, The galois groups of random elements of linear groups, in preparation.
[LSV1] Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Ramanujan complexes of type 𝐴_{𝑑}, Israel J. Math. 149 (2005), 267–299. Probability in mathematics. MR 2191217 (2006i:11134), http://dx.doi.org/10.1007/BF02772543
[LSV2] Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Explicit constructions of Ramanujan complexes of type 𝐴_{𝑑}, European J. Combin. 26 (2005), no. 6, 965–993. MR 2143204 (2006g:20043), http://dx.doi.org/10.1016/j.ejc.2004.06.007
[LS] Alexander Lubotzky and Dan Segal, Subgroup growth, Progress in Mathematics, vol. 212, Birkhäuser Verlag, Basel, 2003. MR 1978431 (2004k:20055)
[LSh] Alexander Lubotzky and Yehuda Shalom, Finite representations in the unitary dual and Ramanujan groups, Discrete geometric analysis, Contemp. Math., vol. 347, Amer. Math. Soc., Providence, RI, 2004, pp. 173–189. MR 2077037 (2005e:22011)
[LW] A. Lubotzky and B. Weiss, Groups and expanders, Expanding graphs (Princeton, NJ, 1992) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 10, Amer. Math. Soc., Providence, RI, 1993, pp. 95–109. MR 1235570 (95b:05097)
[LZ] Alexander Lubotzky and Efim Zelmanov, Dimension expanders, J. Algebra 319 (2008), no. 2, 730–738. MR 2381805 (2008k:05098), http://dx.doi.org/10.1016/j.jalgebra.2005.12.033
[LZi] Alexander Lubotzky and Robert 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), http://dx.doi.org/10.1007/BF02765899
[LZu] A. Lubtozky and A. Zuk, On property $(\tau )$ , monograph in preparation.
[Ma1] Joseph Maher, Random walks on the mapping class group, Duke Math. J. 156 (2011), no. 3, 429–468. MR 2772067, http://dx.doi.org/10.1215/00127094-2010-216
[Ma2] Joseph Maher, Random Heegaard splittings, J. Topol. 3 (2010), no. 4, 997–1025. MR 2746344 (2012d:37087), http://dx.doi.org/10.1112/jtopol/jtq031
[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, Problemy Peredači Informacii 9 (1973), no. 4, 71–80 (Russian). 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), http://dx.doi.org/10.1007/BF02579283
[M3] G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii 24 (1988), no. 1, 51–60 (Russian); English transl., Problems Inform. Transmission 24 (1988), no. 1, 39–46. 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), http://dx.doi.org/10.1112/plms/s3-48.3.514
[Maz] B. Mazur, It is a story, A lecture given at Diaconis' 60th birthday. Available at http://www.math.ucsd.edu/ williams/diaconis/It.is.a.story.3.pdf
[MW] Roy Meshulam and Avi Wigderson, Expanders in group algebras, Combinatorica 24 (2004), no. 4, 659–680. MR 2096820 (2005m:05114), http://dx.doi.org/10.1007/s00493-004-0040-9
[Mo] Moshe Morgenstern, Existence and explicit constructions of 𝑞+1 regular Ramanujan graphs for every prime power 𝑞, J. Combin. Theory Ser. B 62 (1994), no. 1, 44–62. MR 1290630 (95h:05089), http://dx.doi.org/10.1006/jctb.1994.1054
[MR] Alexei G. Myasnikov and Alexander N. Rybalov, Generic complexity of undecidable problems, J. Symbolic Logic 73 (2008), no. 2, 656–673. MR 2414470 (2009g:03068), http://dx.doi.org/10.2178/jsl/1208359065
[NS] Amos Nevo and Peter Sarnak, Prime and almost prime integral points on principal homogeneous spaces, Acta Math. 205 (2010), no. 2, 361–402. MR 2746350 (2011m:22040), http://dx.doi.org/10.1007/s11511-010-0057-4
[Ni] Nikolay Nikolov, A product of decomposition for the classical quasisimple groups, J. Group Theory 10 (2007), no. 1, 43–53. MR 2288458 (2007m:20073), http://dx.doi.org/10.1515/JGT.2007.005
[NiPy] N. Nikolov and L. Pyber, Product decompositions of quasirandom groups and a Jordan type theorem, arXiv:math/0703343
[No] Madhav V. Nori, On subgroups of 𝐺𝐿_{𝑛}(𝐹_{𝑝}), Invent. Math. 88 (1987), no. 2, 257–275. MR 880952 (88d:20068), http://dx.doi.org/10.1007/BF01388909
[Pi] Richard Pink, Strong approximation for Zariski dense subgroups over arbitrary global fields, Comment. Math. Helv. 75 (2000), no. 4, 608–643. MR 1789179 (2001k:20106), http://dx.doi.org/10.1007/s000140050142
[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] Omer Reingold, Salil Vadhan, and Avi 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), http://dx.doi.org/10.2307/3062153
[Ri1] Igor 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), http://dx.doi.org/10.1215/00127094-2008-009
[Ri2] Igor Rivin, Zariski density and genericity, Int. Math. Res. Not. IMRN 19 (2010), 3649–3657. MR 2725508 (2012c:20145), http://dx.doi.org/10.1093/imrn/rnq043
[RSW] Eyal Rozenman, Aner Shalev, and Avi Wigderson, Iterative construction of Cayley expander graphs, Theory Comput. 2 (2006), 91–120. MR 2322872 (2009b:05133), http://dx.doi.org/10.4086/toc.2006.v002a005
[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] Peter Sarnak, Some applications of modular forms, Cambridge Tracts in Mathematics, vol. 99, Cambridge University Press, Cambridge, 1990. MR 1102679 (92k:11045)
[S2] Peter Sarnak, Selberg’s eigenvalue conjecture, Notices Amer. Math. Soc. 42 (1995), no. 11, 1272–1277. MR 1355461 (97c:11059)
[S3] Peter Sarnak, What is…an expander?, Notices Amer. Math. Soc. 51 (2004), no. 7, 762–763. MR 2072849
[S4] Peter Sarnak, Equidistribution and primes, Astérisque 322 (2008), 225–240. Géométrie différentielle, physique mathématique, mathématiques et société. II. MR 2521658 (2010k:11146)
[S5] P. Sarnak, Letter to Lagarias on integral Apollonian packings. Available at http://www.math.princeton.edu/sarnak/
[S6] P. Sarnak, Equidistribution and Primes, (2007) PIMS Lecture. Available at http://www.math.princeton.edu/sarnak/
[S7] P. Sarnak, Primes and orbits, MAA Garden State lecture. Available at http://www.math.princeton.edu/sarnak/
[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, Acta Arith. 4 (1958), 185–208; erratum 5 (1958), 259 (French). MR 0106202 (21 #4936)
[SiSp] Michael Sipser and Daniel A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1710–1722. Codes and complexity. MR 1465731 (98d:94031), http://dx.doi.org/10.1109/18.556667
[Sel] Atle Selberg, On the estimation of Fourier coefficients of modular forms, Proc. Sympos. Pure Math., Vol. VIII, Amer. Math. Soc., Providence, R.I., 1965, pp. 1–15. MR 0182610 (32 #93)
[Se] Jean-Pierre Serre, Le problème des groupes de congruence pour SL2, Ann. of Math. (2) 92 (1970), 489–527 (French). MR 0272790 (42 #7671)
[Sh1] Yehuda Shalom, Expanding graphs and invariant means, Combinatorica 17 (1997), no. 4, 555–575. MR 1645694 (99h:05057), http://dx.doi.org/10.1007/BF01195004
[Sh2] Yehuda Shalom, Expander graphs and amenable quotients, Emerging applications of number theory (Minneapolis, MN, 1996) IMA Vol. Math. Appl., vol. 109, Springer, New York, 1999, pp. 571–581. MR 1691549 (2000h:20059)
[Sh3] Yehuda Shalom, Bounded generation and Kazhdan’s property (T), Inst. Hautes Études Sci. Publ. Math. 90 (1999), 145–168 (2001). MR 1813225 (2001m:22030)
[Sh4] Yehuda Shalom, The algebraization of Kazhdan’s property (T), International Congress of Mathematicians. Vol. II, Eur. Math. Soc., Zürich, 2006, pp. 1283–1310. MR 2275645 (2008a:22003)
[Ta] R. Michael Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory 27 (1981), no. 5, 533–547. MR 650686 (83i:94017), http://dx.doi.org/10.1109/TIT.1981.1056404
[TV] Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012 (2008a:11002)
[Ti] J. Tits, Free subgroups in linear groups, J. Algebra 20 (1972), 250–270. MR 0286898 (44 #4105)
[Va1] Alain Valette, An application of Ramanujan graphs to 𝐶*-algebra tensor products, Discrete Math. 167/168 (1997), 597–603. 15th British Combinatorial Conference (Stirling, 1995). MR 1446777 (98d:46066), http://dx.doi.org/10.1016/S0012-365X(96)00260-9
[Va2] Alain Valette, Graphes de Ramanujan et applications, Astérisque 245 (1997), Exp. No. 829, 4, 247–276 (French, with French summary). Séminaire Bourbaki, Vol. 1996/97. MR 1627114 (99k:11079)
[Va3] Alain Valette, Introduction to the Baum-Connes conjecture, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2002. From notes taken by Indira Chatterji; With an appendix by Guido Mislin. MR 1907596 (2003f:58047)
[V] P.O. Varju, Expansion in $\mathrm {SL}_d(O_K/I)$ , square-free, arXiv:1001.3664.
[W] Boris 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), http://dx.doi.org/10.2307/2006943
[Z1] P. G. Zograf, Small eigenvalues of automorphic Laplacians in spaces of cusp forms, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 134 (1984), 157–168 (Russian, with English summary). Automorphic functions and number theory, II. 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), http://dx.doi.org/10.1515/crll.1991.414.113
[Z] A. Żuk, Property (T) and Kazhdan constants for discrete groups, Geom. Funct. Anal. 13 (2003), no. 3, 643–670. MR 1995802 (2004m:20079), http://dx.doi.org/10.1007/s00039-003-0425-8

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|