Expander graphs in pure and applied mathematics

Lubotzky, Alexander

doi:10.1090/S0273-0979-2011-01359-3

Expander graphs in pure and applied mathematics
HTML articles powered by AMS MathViewer

by Alexander Lubotzky PDF

Bull. Amer. Math. Soc. 49 (2012), 113-162 Request permission

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

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, DOI 10.4171/GGD/124
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
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, DOI 10.1016/0012-365X(88)90189-6
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
L. Babai, G. Hetyei, W. M. Kantor, A. Lubotzky, and Á. Seress, On the diameter of finite groups, 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990) IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, pp. 857–865. MR 1150735, DOI 10.1109/FSCS.1990.89608
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, DOI 10.1016/S0195-6698(89)80067-8
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
Laurent Bartholdi, On amenability of group algebras. I, Israel J. Math. 168 (2008), 153–165. MR 2448055, DOI 10.1007/s11856-008-1061-7
F. Bassino, A. Martino, C. Nicaud, E. Ventura and P. Weil, Statistical properties of subgroups of free groups, arXiv:1001.4472
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, DOI 10.1515/form.1999.021
E.J. Benveniste and S.J. Szarek, Property $T$, property $\tau$ and irreducibility of matrices, preprint.
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, DOI 10.1016/j.crma.2009.02.009
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, DOI 10.4171/077-1/11
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, DOI 10.1090/S0894-0347-2011-00707-8
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, DOI 10.1016/j.crma.2007.04.017
Jean Bourgain and Alex Gamburd, Uniform expansion bounds for Cayley graphs of $\textrm {SL}_2(\Bbb F_p)$, Ann. of Math. (2) 167 (2008), no. 2, 625–642. MR 2415383, DOI 10.4007/annals.2008.167.625
Jean Bourgain and Alex Gamburd, On the spectral gap for finitely-generated subgroups of $\rm SU(2)$, Invent. Math. 171 (2008), no. 1, 83–121. MR 2358056, DOI 10.1007/s00222-007-0072-z
Jean Bourgain and Alex Gamburd, Expansion and random walks in $\textrm {SL}_d(\Bbb Z/p^n\Bbb Z)$. I, J. Eur. Math. Soc. (JEMS) 10 (2008), no. 4, 987–1011. MR 2443926, DOI 10.4171/JEMS/137
Jean Bourgain and Alex Gamburd, Expansion and random walks in $\textrm {SL}_d(\Bbb Z/p^n\Bbb Z)$. II, J. Eur. Math. Soc. (JEMS) 11 (2009), no. 5, 1057–1103. With an appendix by Bourgain. MR 2538500, DOI 10.4171/JEMS/175
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, DOI 10.1016/j.crma.2006.05.023
Jean Bourgain, Alex Gamburd, and Peter Sarnak, Affine linear sieve, expanders, and sum-product, Invent. Math. 179 (2010), no. 3, 559–644. MR 2587341, DOI 10.1007/s00222-009-0225-3
J. Bourgain, A. Gamburd and P. Sarnak, Generalization of Selberg’s $3/16$ Theorem and Affine Sieve, arXiv:0912.5021
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, DOI 10.1007/s00039-004-0451-1
Jean Bourgain and Alex Kontorovich, On representations of integers in thin subgroups of $\textrm {SL}_2(\Bbb Z)$, Geom. Funct. Anal. 20 (2010), no. 5, 1144–1174. MR 2746949, DOI 10.1007/s00039-010-0093-4
J. Bourgain and P.P. Varju, Expansion in $\mathrm {SL}_d(Z/qZ)$, $q$ arbitrary, arXiv:1006.3365
E. Breuillard, Y. De Cornulier, A. Lubotzky and C. Meiri, Conjugacy growth of linear groups. arXiv:1106.4773
Emmanuel Breuillard and Alex Gamburd, Strong uniform expansion in $\textrm {SL}(2,p)$, Geom. Funct. Anal. 20 (2010), no. 5, 1201–1209. MR 2746951, DOI 10.1007/s00039-010-0094-3
Emmanuel Breuillard, Ben Green, and Terence Tao, Linear approximate groups, Electron. Res. Announc. Math. Sci. 17 (2010), 57–67. MR 2718104, DOI 10.3934/era.2010.17.57
E. Breuillard, B. Green and T. Tao, Approximate subgroups of linear groups, arXiv:1005.1881
Emmanuel Breuillard, Ben Green, and Terence Tao, Suzuki groups as expanders, Groups Geom. Dyn. 5 (2011), no. 2, 281–299. MR 2782174, DOI 10.4171/GGD/128
E. Breuillard, B. Green, R. Guralnick and T. Tao, Strongly dense free subgroups of semisimple algebraic groups, arXiv:1010.4259
E. Breuillard, B. J. Green, R. Guralnick and T. C. Tao, Expansion in finite simple groups of Lie type, in preparation.
M. R. Buettgens, Property $\tau$ and von Neumann algebras, Thesis, State University of New York at Buffalo, 2009. MR2712779
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
M. Burger and P. Sarnak, Ramanujan duals. II, Invent. Math. 106 (1991), no. 1, 1–11. MR 1123369, DOI 10.1007/BF01243900
Peter Buser, Geometry and spectra of compact Riemann surfaces, Progress in Mathematics, vol. 106, Birkhäuser Boston, Inc., Boston, MA, 1992. MR 1183224
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, DOI 10.1080/00927879508825509
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 434997
Laurent Clozel, Démonstration de la conjecture $\tau$, Invent. Math. 151 (2003), no. 2, 297–328 (French). MR 1953260, DOI 10.1007/s00222-002-0253-8
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, DOI 10.1017/CBO9780511615825
P. Diaconis and L. Saloff-Coste, Walks on generating sets of groups, Invent. Math. 134 (1998), no. 2, 251–299. MR 1650316, DOI 10.1007/s002220050265
Oren Dinai, Growth in $\textrm {SL}_2$ over finite fields, J. Group Theory 14 (2011), no. 2, 273–297. MR 2788087, DOI 10.1515/JGT.2010.056
John D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199–205. MR 251758, DOI 10.1007/BF01110210
Nathan M. Dunfield and William P. Thurston, Finite covers of random 3-manifolds, Invent. Math. 166 (2006), no. 3, 457–521. MR 2257389, DOI 10.1007/s00222-006-0001-6
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, DOI 10.1109/CCC.2008.19
Gábor Elek, The amenability of affine algebras, J. Algebra 264 (2003), no. 2, 469–478. MR 1981416, DOI 10.1016/S0021-8693(03)00163-7
J. Ellenberg, C. Hall and E. Kowalski, Expander graphs, gonality and variation of Galois representations, arXiv:1008.3675
J. S. Ellenberg, P. Michel and A. Venkatesh, Linnik’s ergodic method and the distribution of integer points on spheres, arXiv:1001.0897
Mikhail Ershov, Golod-Shafarevich groups with property $(T)$ and Kac-Moody groups, Duke Math. J. 145 (2008), no. 2, 309–339. MR 2449949, DOI 10.1215/00127094-2008-053
Mikhail Ershov and Andrei Jaikin-Zapirain, Property (T) for noncommutative universal lattices, Invent. Math. 179 (2010), no. 2, 303–347. MR 2570119, DOI 10.1007/s00222-009-0218-2
J. Fox, M. Gromov, V. Lafforgue, A. Naor and J. Pach, Overlap properties of geometric expanders, arXiv:1005.1392
John Friedlander and Henryk Iwaniec, Opera de cribro, American Mathematical Society Colloquium Publications, vol. 57, American Mathematical Society, Providence, RI, 2010. MR 2647984, DOI 10.1090/coll/057
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, DOI 10.1090/memo/0910
E. Fuchs, Ph.D. Thesis, Princeton University.
E. Fuchs and K. Sanden, Some experiments with integral Apollonian circle packings, arXiv:1001.1406
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, DOI 10.1007/s002229900019
Damien Gaboriau, What is $\ldots$ cost?, Notices Amer. Math. Soc. 57 (2010), no. 10, 1295–1296. MR 2761803
Alex Gamburd, On the spectral gap for infinite index “congruence” subgroups of $\textrm {SL}_2(\mathbf Z)$, Israel J. Math. 127 (2002), 157–200. MR 1900698, DOI 10.1007/BF02784530
Alex Gamburd, Expander graphs, random matrices and quantum chaos, Random walks and geometry, Walter de Gruyter, Berlin, 2004, pp. 109–140. MR 2087781
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, DOI 10.1002/rsa.20266
Alex Gamburd, Dmitry Jakobson, and Peter Sarnak, Spectra of elements in the group ring of $\textrm {SU}(2)$, J. Eur. Math. Soc. (JEMS) 1 (1999), no. 1, 51–85. MR 1677685, DOI 10.1007/PL00011157
N. Gill and H.A. Helfgott, Growth of small generating sets in $\mathrm {SL}_n(Z/pZ)$, arXiv:1002.1605
G. Glauberman, Factorizations in local subgroups of finite groups, Regional Conference Series in Mathematics, No. 33, American Mathematical Society, Providence, R.I., 1977. MR 0470072
W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363–387. MR 2410393, DOI 10.1017/S0963548307008826
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, DOI 10.1016/S0022-314X(03)00015-5
B. Green, Approximate groups and their applications: work of Bourgain, Gamburd, Helfgott and Sarnak, arXiv:0911.3354
Ben Green and Terence Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481–547. MR 2415379, DOI 10.4007/annals.2008.167.481
Benjamin Green and Terence Tao, Linear equations in primes, Ann. of Math. (2) 171 (2010), no. 3, 1753–1850. MR 2680398, DOI 10.4007/annals.2010.171.1753
B. Green, T. Tao and T. Ziegler, An inverse theorem for the Gowers $U^{s+1}[N]$-norm. arXiv:1009.3998
M. Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003), no. 1, 73–146. MR 1978492, DOI 10.1007/s000390300002
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, DOI 10.1007/s00039-009-0021-7
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, DOI 10.1007/s00039-010-0073-8
M. Gromov and L. Guth, Generalizations of the Kolmogorov-Barzdin embedding estimates, arXiv:1103.3423
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, DOI 10.1007/s00039-009-0702-2
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, DOI 10.1007/BF02403921
H. A. Helfgott, Growth and generation in $\textrm {SL}_2(\Bbb Z/p\Bbb Z)$, Ann. of Math. (2) 167 (2008), no. 2, 601–623. MR 2415382, DOI 10.4007/annals.2008.167.601
H. A. Helfgott, Growth in $\textrm {SL}_3(\Bbb Z/p\Bbb Z)$, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 3, 761–851. MR 2781932, DOI 10.4171/JEMS/267
N. Higson, V. Lafforgue, and G. Skandalis, Counterexamples to the Baum-Connes conjecture, Geom. Funct. Anal. 12 (2002), no. 2, 330–354. MR 1911663, DOI 10.1007/s00039-002-8249-5
Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
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, DOI 10.1090/S0002-9947-96-01456-0
Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214, DOI 10.1090/coll/053
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
William M. Kantor and Alexander Lubotzky, The probability of generating a finite classical group, Geom. Dedicata 36 (1990), no. 1, 67–87. MR 1065213, DOI 10.1007/BF00181465
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.
Ilya Kapovich, Alexei Myasnikov, 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, DOI 10.1016/S0021-8693(03)00167-4
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, DOI 10.1016/j.aim.2003.02.001
Ilya Kapovich and Paul Schupp, On group-theoretic models of randomness and genericity, Groups Geom. Dyn. 2 (2008), no. 3, 383–404. MR 2415305, DOI 10.4171/GGD/45
Martin Kassabov, Universal lattices and unbounded rank expanders, Invent. Math. 170 (2007), no. 2, 297–326. MR 2342638, DOI 10.1007/s00222-007-0064-z
Martin Kassabov, Symmetric groups and expander graphs, Invent. Math. 170 (2007), no. 2, 327–354. MR 2342639, DOI 10.1007/s00222-007-0065-y
Martin Kassabov, Alexander Lubotzky, and Nikolay Nikolov, Finite simple groups as expanders, Proc. Natl. Acad. Sci. USA 103 (2006), no. 16, 6116–6119. MR 2221038, DOI 10.1073/pnas.0510337103
Martin Kassabov and Nikolay Nikolov, Universal lattices and property tau, Invent. Math. 165 (2006), no. 1, 209–224. MR 2221141, DOI 10.1007/s00222-005-0498-0
T. Kaufman and A. Lubotzky, Edge transitive Ramanujan graphs and highly symmetric LDPC good codes, arXiv:1108.2960.
T. Kaufman and A. Wigderson, Symmetric LDPC and local Testing, Innovations in Computer Science, 406–421, 2010.
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
Henry H. Kim, Functoriality for the exterior square of $\textrm {GL}_4$ and the symmetric fourth of $\textrm {GL}_2$, J. Amer. Math. Soc. 16 (2003), no. 1, 139–183. With appendix 1 by Dinakar Ramakrishnan and appendix 2 by Kim and Peter Sarnak. MR 1937203, DOI 10.1090/S0894-0347-02-00410-1
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ārzdiņš], 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
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, DOI 10.1090/S0894-0347-2011-00691-7
A. Kontorovich and H. Oh, Almost prime Pythagorean triples in thin orbits, arXiv:1001.0370
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, DOI 10.1017/CBO9780511542947
E. Kowalski, Amplification arguments for large sieve inequalities, Arch. Math. (Basel) 94 (2010), no. 5, 443–457. MR 2643980, DOI 10.1007/s00013-010-0122-4
Marc Lackenby, Expanders, rank and graphs of groups, Israel J. Math. 146 (2005), 357–370. MR 2151608, DOI 10.1007/BF02773541
Marc Lackenby, A characterisation of large finitely presented groups, J. Algebra 287 (2005), no. 2, 458–473. MR 2134155, DOI 10.1016/j.jalgebra.2005.03.004
Marc Lackenby, Heegaard splittings, the virtually Haken conjecture and property $(\tau )$, Invent. Math. 164 (2006), no. 2, 317–359. MR 2218779, DOI 10.1007/s00222-005-0480-x
Marc Lackenby, Large groups, property $(\tau )$ and the homology growth of subgroups, Math. Proc. Cambridge Philos. Soc. 146 (2009), no. 3, 625–648. MR 2496348, DOI 10.1017/S0305004108002089
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, DOI 10.2140/gt.2008.12.2047
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, DOI 10.1093/imrn/rnn036
Gilbert Levitt, On the cost of generating an equivalence relation, Ergodic Theory Dynam. Systems 15 (1995), no. 6, 1173–1181. MR 1366313, DOI 10.1017/S0143385700009846
Martin W. Liebeck and Aner Shalev, The probability of generating a finite simple group, Geom. Dedicata 56 (1995), no. 1, 103–113. MR 1338320, DOI 10.1007/BF01263616
T. Li, Rank and genus of $3$-manifolds. arXiv:1106.6302v1
Nathan Linial, Finite metric-spaces—combinatorics, geometry and algorithms, Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 573–586. MR 1957562
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, DOI 10.1112/jtopol/jtm010
Eduard Looijenga, Prym representations of mapping class groups, Geom. Dedicata 64 (1997), no. 1, 69–83. MR 1432535, DOI 10.1023/A:1004909416648
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, DOI 10.1007/978-3-0346-0332-4
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, DOI 10.1017/CBO9780511662096.008
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, DOI 10.2307/2118597
Alexander Lubotzky, Free quotients and the first Betti number of some hyperbolic manifolds, Transform. Groups 1 (1996), no. 1-2, 71–82. MR 1390750, DOI 10.1007/BF02587736
Alex Lubotzky, What is$\dots$property $(\tau )$?, Notices Amer. Math. Soc. 52 (2005), no. 6, 626–627. MR 2147485
A. Lubotzky, Finite simple groups of Lie type as expanders, J. Eur. Math. Soc. 13 (2011), 1331–1341.
A. Lubotzky and C. Meiri, Sieve methods in group theory: I. powers in linear groups. Geom. Dedicata, to appear.arXiv:1107.3666
A. Lubotzky and C. Meiri, Sieve methods in group theory: II. The mapping class group. arXiv:1104:2450
A. Lubotzky and C. Meiri, Sieve methods in group theory: III. $Aut(F_n)$. arXiv:1104:2450
Alexander Lubotzky and Igor Pak, The product replacement algorithm and Kazhdan’s property (T), J. Amer. Math. Soc. 14 (2001), no. 2, 347–363. MR 1815215, DOI 10.1090/S0894-0347-00-00356-8
A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan conjecture and explicit construction of expanders, Proc. STOC. 86 (1986), 240–246.
A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
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, DOI 10.1002/cpa.3160390710
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, DOI 10.1002/cpa.3160400402
A. Lubotzky and L. Rosenzweig, The galois groups of random elements of linear groups, in preparation.
Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Ramanujan complexes of type $\~A_d$, Israel J. Math. 149 (2005), 267–299. Probability in mathematics. MR 2191217, DOI 10.1007/BF02772543
Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Explicit constructions of Ramanujan complexes of type $\~A_d$, European J. Combin. 26 (2005), no. 6, 965–993. MR 2143204, DOI 10.1016/j.ejc.2004.06.007
Alexander Lubotzky and Dan Segal, Subgroup growth, Progress in Mathematics, vol. 212, Birkhäuser Verlag, Basel, 2003. MR 1978431, DOI 10.1007/978-3-0348-8965-0
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, DOI 10.1090/conm/347/06272
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, DOI 10.1090/dimacs/010/08
Alexander Lubotzky and Efim Zelmanov, Dimension expanders, J. Algebra 319 (2008), no. 2, 730–738. MR 2381805, DOI 10.1016/j.jalgebra.2005.12.033
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, DOI 10.1007/BF02765899
A. Lubtozky and A. Zuk, On property $(\tau )$, monograph in preparation.
Joseph Maher, Random walks on the mapping class group, Duke Math. J. 156 (2011), no. 3, 429–468. MR 2772067, DOI 10.1215/00127094-2010-216
Joseph Maher, Random Heegaard splittings, J. Topol. 3 (2010), no. 4, 997–1025. MR 2746344, DOI 10.1112/jtopol/jtq031
J. Malestein and J. Souto, On genericity of pseudo-Anosovs in the Torelli group, arXiv:1102.0601
G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71–80 (Russian). MR 0484767
G. A. Margulis, Explicit constructions of graphs without short cycles and low density codes, Combinatorica 2 (1982), no. 1, 71–78. MR 671147, DOI 10.1007/BF02579283
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
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, DOI 10.1112/plms/s3-48.3.514
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
Roy Meshulam and Avi Wigderson, Expanders in group algebras, Combinatorica 24 (2004), no. 4, 659–680. MR 2096820, DOI 10.1007/s00493-004-0040-9
Moshe Morgenstern, Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$, J. Combin. Theory Ser. B 62 (1994), no. 1, 44–62. MR 1290630, DOI 10.1006/jctb.1994.1054
Alexei G. Myasnikov and Alexander N. Rybalov, Generic complexity of undecidable problems, J. Symbolic Logic 73 (2008), no. 2, 656–673. MR 2414470, DOI 10.2178/jsl/1208359065
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, DOI 10.1007/s11511-010-0057-4
Nikolay Nikolov, A product of decomposition for the classical quasisimple groups, J. Group Theory 10 (2007), no. 1, 43–53. MR 2288458, DOI 10.1515/JGT.2007.005
N. Nikolov and L. Pyber, Product decompositions of quasirandom groups and a Jordan type theorem, arXiv:math/0703343
Madhav V. Nori, On subgroups of $\textrm {GL}_n(\textbf {F}_p)$, Invent. Math. 88 (1987), no. 2, 257–275. MR 880952, DOI 10.1007/BF01388909
Richard Pink, Strong approximation for Zariski dense subgroups over arbitrary global fields, Comment. Math. Helv. 75 (2000), no. 4, 608–643. MR 1789179, DOI 10.1007/s000140050142
M.S. Pinsker, On the complexity of a concentrator, 7th International Teletraffic Conference, Stockholm, pages 318/1–318/4, June 1973.
L. Pyber and E. Szabó, Growth in finite simple groups of Lie type, arXiv:1001.4556
L. Pyber and E. Szabó, Growth in finite simple groups of Lie type of bounded rank, arXiv:1005.1858
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, DOI 10.2307/3062153
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, DOI 10.1215/00127094-2008-009
Igor Rivin, Zariski density and genericity, Int. Math. Res. Not. IMRN 19 (2010), 3649–3657. MR 2725508, DOI 10.1093/imrn/rnq043
Eyal Rozenman, Aner Shalev, and Avi Wigderson, Iterative construction of Cayley expander graphs, Theory Comput. 2 (2006), 91–120. MR 2322872, DOI 10.4086/toc.2006.v002a005
A. Salehi Golsefidy and P. Sarnak, Affine linear sieve, arXiv:1109.6432.
A. Salehi Golsefidy and P. Varju, Expansion in perfect groups, arXiv:1108.4900.
Peter Sarnak, Some applications of modular forms, Cambridge Tracts in Mathematics, vol. 99, Cambridge University Press, Cambridge, 1990. MR 1102679, DOI 10.1017/CBO9780511895593
Peter Sarnak, Selberg’s eigenvalue conjecture, Notices Amer. Math. Soc. 42 (1995), no. 11, 1272–1277. MR 1355461
Peter Sarnak, What is$\dots$an expander?, Notices Amer. Math. Soc. 51 (2004), no. 7, 762–763. MR 2072849
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
P. Sarnak, Letter to Lagarias on integral Apollonian packings. Available at http://www.math.princeton.edu/sarnak/
P. Sarnak, Equidistribution and Primes, (2007) PIMS Lecture. Available at http://www.math.princeton.edu/sarnak/
P. Sarnak, Primes and orbits, MAA Garden State lecture. Available at http://www.math.princeton.edu/sarnak/
P. Sarnak, Integral Apollonian Packings - MAA Lecture January 2009. Available at http://www.math.princeton
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 106202, DOI 10.4064/aa-4-3-185-208
Michael Sipser and Daniel A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1710–1722. Codes and complexity. MR 1465731, DOI 10.1109/18.556667
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
Jean-Pierre Serre, Le problème des groupes de congruence pour SL2, Ann. of Math. (2) 92 (1970), 489–527 (French). MR 272790, DOI 10.2307/1970630
Yehuda Shalom, Expanding graphs and invariant means, Combinatorica 17 (1997), no. 4, 555–575. MR 1645694, DOI 10.1007/BF01195004
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, DOI 10.1007/978-1-4612-1544-8_{2}3
Yehuda Shalom, Bounded generation and Kazhdan’s property (T), Inst. Hautes Études Sci. Publ. Math. 90 (1999), 145–168 (2001). MR 1813225
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
R. Michael Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory 27 (1981), no. 5, 533–547. MR 650686, DOI 10.1109/TIT.1981.1056404
Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
J. Tits, Free subgroups in linear groups, J. Algebra 20 (1972), 250–270. MR 286898, DOI 10.1016/0021-8693(72)90058-0
Alain Valette, An application of Ramanujan graphs to $C^*$-algebra tensor products, Discrete Math. 167/168 (1997), 597–603. 15th British Combinatorial Conference (Stirling, 1995). MR 1446777, DOI 10.1016/S0012-365X(96)00260-9
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
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, DOI 10.1007/978-3-0348-8187-6
P.O. Varju, Expansion in $\mathrm {SL}_d(O_K/I)$, $I$ square-free, arXiv:1001.3664.
Boris Weisfeiler, Strong approximation for Zariski-dense subgroups of semisimple algebraic groups, Ann. of Math. (2) 120 (1984), no. 2, 271–315. MR 763908, DOI 10.2307/2006943
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
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, DOI 10.1515/crll.1991.414.113
A. Żuk, Property (T) and Kazhdan constants for discrete groups, Geom. Funct. Anal. 13 (2003), no. 3, 643–670. MR 1995802, DOI 10.1007/s00039-003-0425-8