Uniform expansion bounds for Cayley graphs of SL<sub>2</sub>(𝔽<sub>p</sub>)

Jean Bourgain, Alex Gamburd

Type: Article

Publication Date: 2008-03-01

Citations: 266

DOI: https://doi.org/10.4007/annals.2008.167.625

Abstract

We prove that Cayley graphs of SL 2 (F p ) are expanders with respect to the projection of any fixed elements in SL(2, Z) generating a non-elementary subgroup, and with respect to generators chosen at random in SL 2 (F p ).

Locations

Annals of Mathematics - View - PDF
Annals of Mathematics - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Strong Uniform Expansion in SL(2, p)	2010	Emmanuel Breuillard Alex Gamburd
+	Strong uniform expansion in $\mathrm{SL}(2,p)$	2009	Emmanuel Breuillard Alex Gamburd
+ PDF	Expanders In Group Algebras	2004	Roy Meshulam Avi Wigderson
+ PDF	Expansion and random walks in SLd(ℤ/pnℤ): I	2008	Jean Bourgain Alex Gamburd
+	Expanders graphs and sieving in combinatorial structures	2012	Florent Jouve Jean‐Sébastien Sereni
+ PDF	Expansion and random walks in $\mathrm{SL}_d(\mathbb{Z}/p^n \mathbb{Z})$: II	2009	Jean Bourgain Alex Gamburd
+	Random Cayley graphs and expanders	1994	Noga Alon Yuval Roichman
+ PDF	EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES	2018	Florent Jouve Jean‐Sébastien Sereni
+	Expanders and Related Results	2011	Shotaro Makisumi
+	Parameterized (Modular) Counting and Cayley Graph Expanders	2021	Norbert Peyerimhoff Marc Roth Johannes Schmitt Jakob Stix Alina Vdovina
+	Parameterized (Modular) Counting and Cayley Graph Expanders	2021	Norbert Peyerimhoff Marc Roth Johannes Schmitt Jakob Stix Alina Vdovina
+	Random Cayley Graphs with O(log\|G\|) Generators Are Expanders	1999	Igor Pak
+	Diameters of Cayley graphs of SL_n(Z/kZ)	2005	Martin Kassabov Tim Riley
+	Expansion, Random Walks and Sieving in $SL_2 (\mathbb{F}_p [t])$	2015	Henry Bradford
+	Expansion, Random Walks and Sieving in $SL_2 (\mathbb{F}_p [t])$	2015	H. F. Bradford
+	Explicit growth and expansion for SL_2	2012	Emmanuel Kowalski
+	Explicit growth and expansion for SL_2	2012	Emmanuel Kowalski
+	Cayley Graph Expanders and Groups of Finite Width	2008	Norbert Peyerimhoff Alina Vdovina
+ PDF Chat	Expansion in perfect groups	2012	Alireza Salehi Golsefidy Péter P. Varjú
+	Parameterized Counting and Cayley Graph Expanders	2023	Norbert Peyerimhoff Marc Roth Johannes Schmitt Jakob Stix Alina Vdovina Philip Wellnitz

Works That Cite This (260)

Action	Title	Year	Authors
+ PDF	Hamiltonian paths in Cayley graphs	2009	Igor Pak Radoš Radoičić
+	Markoff triples and strong approximation	2016	Jean Bourgain Alexander Gamburd Peter Sarnak
+	The chromatic number of random Cayley graphs	2013	Noga Alon
+	Growth in finite simple groups of Lie type	2014	László Pyber Endre Szabó
+	Super-approximation, II: the p-adic and bounded power of square-free integers cases	2016	Alireza Salehi Golsefidy
+ PDF Chat	$${\text {SL}}_2$$ SL 2 homomorphic hash functions: worst case to average case reduction and short collision search	2015	Ciarán Mullan Boaz Tsaban
+	Equidistribution and primes	2008	Peter Sarnak
+ PDF	From Apollonius to Zaremba: Local-global phenomena in thin orbits	2013	Alex Kontorovich
+ PDF Chat	Expansion in SL d (Z/q Z), q arbitrary	2011	Jean Bourgain Péter P. Varjú
+	Uniform exponential mixing and resonance free regions for convex cocompact congruence subgroups of $\operatorname{SL}_2(\mathbb{Z})$	2014	Hee Oh Dale Winter

Works Cited by This (25)

Action	Title	Year	Authors
+	Cayley graphs: eigenvalues, expanders and random walks	1995	Alexander Lubotzky
+	Numerical investigation of the spectrum for certain families of Cayley graphs	1993	John Lafferty Daniel N. Rockmore
+	Level Spacings for Cayley Graphs	1999	John Lafferty Daniel N. Rockmore
+	Geometry of Discrete Groups	2006	Alan F. Beardon
+	Elementary Number Theory, Group Theory and Ramanujan Graphs	2001	Giuliana P. Davidoff Peter Sarnak Alain Valette
+ PDF	Growth and generation in SL<sub>2</sub>(ℤ∕pℤ)	2008	H. A. Helfgott
+	Expanding graphs and invariant means	1997	Yehuda Shalom
+	On the spectral gap for infinite index “congruence” subgroups of SL2(Z)	2002	Alex Gamburd
+	None	2009	Alex Gamburd Shlomo Hoory Mehrdad Shahshahani Aner Shalev Bálint Virág
+ PDF Chat	A sum-product estimate in finite fields, and applications	2004	Jean Bourgain Nets Hawk Katz Terence Tao