×

Strong uniform expansion in \(\text{SL}(2,p)\). (English) Zbl 1253.20051

Expanders are highly connected sparse graphs widely used in computer science; they also have found some remarkable applications in pure mathematics. A basic problem formulated by Lubotzky and Weiss in 1993 is to what extent the expansion property is a property of the family of groups \( \{G_i\}\) alone, independent of the choice of generators.
In this paper, the authors show that there is an infinite set of primes \(\mathcal P\) of density one, such that the family of all Cayley graphs of \(\text{SL}(2,p)\), \(p\in\mathcal P\), is a family of expanders.

MSC:

20G40 Linear algebraic groups over finite fields
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
60B99 Probability theory on algebraic and topological structures

Citations:

Zbl 0787.05049
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abert M., Babai L.: Finite groups of uniform logarithmic diameter. Israel J. Math. 158, 193–203 (2007) · Zbl 1145.20022 · doi:10.1007/s11856-007-0009-7
[2] N. Alon, A. Lubotzky, A. Wigderson, Semi-direct product in groups and zig-zag product in graphs: Connections and applications, Proc. of the 42nd FOCS (2001), 630–637.
[3] E. Breuillard, A strong Tits alternative, preprint (2008); arXiv:0804.1395
[4] E. Breuillard, Heights on SL(2) and free subgroups, Zimmer’s Festschrift, Chicago Univ. Press, to appear. · Zbl 1261.20047
[5] Bourgain J., Gamburd A.: Uniform expansion bounds for Cayley graphs of \({{\mathrm SL}_2(\mathbb {F}_p)}\) . Annals of Mathematics 167, 625–642 (2008) · Zbl 1216.20042 · doi:10.4007/annals.2008.167.625
[6] Celler F., Leedham-Green C.R., Murray S., Niemeyer A., O’Brien E.A.: Generating random elements of a finite group. Comm. Algebra 23, 4931–4948 (1995) · Zbl 0836.20094 · doi:10.1080/00927879508825509
[7] Gamburd A., Pak I.: Expansion of product replacement graphs. Combinatorica 26, 411–429 (2006) · Zbl 1121.05114 · doi:10.1007/s00493-006-0023-0
[8] Gilman R.: Finite quotients of the automorphism group of a free group. Canad. J. Math. 29, 541–551 (1977) · Zbl 0344.20025 · doi:10.4153/CJM-1977-056-3
[9] G. Hoheisel, Primzahlprobleme in der analysis, S-B Preuss. Akad. Wiss. Phys.- Math. Kl (1930), 580–588.
[10] Hoory S., Linial N., Wigderson A.: Expander graphs and their applications. Bull. Amer. Math Soc. 43, 439–561 (2006) · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8
[11] Huxley M.N.: On the difference between consecutive primes. Invent. Math. 15, 164–170 (1972) · Zbl 0241.10026 · doi:10.1007/BF01418933
[12] Kassabov M.: Symmetric groups and expander graphs. Invent. Math. 170, 327–354 (2007) · Zbl 1191.20002 · doi:10.1007/s00222-007-0065-y
[13] Kesten H.: Symmetric random walks on groups. Trans. AMS 92, 336–354 (1959) · Zbl 0092.33503 · doi:10.1090/S0002-9947-1959-0109367-6
[14] E. Kowalski, H. Iwaniec, Analytic Number Theory, AMS Colloquium Publication 53 (YEAR). · Zbl 1059.11001
[15] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Progress in Mathematics 195, Birkhäuser (1994). · Zbl 0826.22012
[16] A. Lubotzky, Cayley graphs: eigenvalues, expanders and random walks, Surveys in Combinatorics (P. Rowbinson, ed.), London Math. Soc. Lecture Note Ser. 218, Cambridge Univ. Press (1995), 155–189. · Zbl 0835.05033
[17] Lubotzky A., Pak I.: The product replacement algorithm and Kazhdan’s property (T). Journal of AMS 52, 5525–5561 (2000)
[18] Lubotzky A., Phillips R., Sarnak P.: Ramanujan graphs. Combinatorica 8, 261–277 (1988) · Zbl 0661.05035 · doi:10.1007/BF02126799
[19] A. Lubotzky, B. Weiss, Groups and Expanders, in ”DIMACS Series in Disc. Math. and Theor. Comp. Sci. 10 (J. Friedman, ed.) (1993), 95–109. · Zbl 0787.05049
[20] Margulis G.A.: Explicit constructions of concentrators. Probl. of Inform. Transm. 10, 325–332 (1975)
[21] Margulis G.A.: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Probl. of Inform. Trans. 24, 39–46 (1988) · Zbl 0708.05030
[22] D.W. Masser, G. Wustholz, Fields of large transcendence degree generated by values of elliptic functions, Invent. Math. (1983), 407–464. · Zbl 0516.10027
[23] I. Pak, What do we know about the product replacement algorithm?, in ”Groups and Computation III” (W. Kantor, A. Seress, eds.), Berlin (2000), 301–347. · Zbl 0986.68172
[24] Reingold O., Vadhan S., Wigderson A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics 155(1), 157–187 (2002) · Zbl 1008.05101 · doi:10.2307/3062153
[25] Sarnak P.: What is an expander?. Notices of the American Mathematical Society 51, 762–763 (2004) · Zbl 1161.05341
[26] Suzuki M.: Group Theory I. Springer-Verlag, Berlin-Heidelberg-New York (1982) · Zbl 0472.20001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.