Abstract
Let G be a finite group. Choose a set S of size k uniformly from G and consider a lazy random walk on the corresponding Cayley graph Γ (G,S). We show that for almost all choices of S given k = 2alog2 |G|, a > 1, we have Reλ1 ≤ 1-1/2a. A similar but weaker result was obtained earlier by Alon and Roichman (see [4]).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Aldous, P. Diaconis: Shuffling cards and stopping times, Amer. Math. Monthly, 93 1986, pp 333–348.
D. Aldous, P. Diaconis: Strong uniform times and finite random walks, Adv. Appl. Math., 8 1987, pp 69–97.
D. Aldous, J. Fill: Reversible Markov Chains and RandomWalks on Graphs monograph in preparation 1996.
N. Alon, Y. Roichman: Random Cayley graphs and expanders, Rand. Str. Alg., 5 1994, pp 271–284.
L. Babai: Local expansion of vertex-transitive graphs and randomgeneartion in finite groups, in Proc 23rd ACMSTOC 1991, pp 164–174.
L. Babai: Automorphismgroups, isomorphism, reconstruction, in Handbookof Combinatorics (R. L. Grahamet al., eds.), Elsevier 1996.
P. Diaconis: Group Representations in Probability and Statistics, IMS, Hayward, California 1988.
C. Dou, M. Hildebrand: Enumeration and randomrandomwalks on finite groups, Ann. Prob., 24 1996, pp 987–1000.
P. Erdos, R. R. Hall: Probabilistic methods in group theory. II, Houston J. Math., 2 1976, pp 173–180.
P. Erdös, A. Rényi: Probabilistic methods in group theory, Jour. Analyse Mathématique, 14 1965, pp 127–138.
I. Pak: Random walks on groups: strong uniform time approach, Ph.D. Thesis, Harvard U. 1997.
I. Pak: Random walks on finite groups with few random generators, Electronic J. Prob., 4 1999, pp 1–11.
Y. Roichman: On random random walks, Ann. Prob., 24 1996, pp 1001–1011.
D. Wilson: Random random walks on ℤ 2d , Prob. Th. Rel. Fields, 108 1997, pp 441–457.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pak, I. (1999). Random Cayley Graphs with O(log|G|) Generators Are Expanders. In: Nešetřil, J. (eds) Algorithms - ESA’ 99. ESA 1999. Lecture Notes in Computer Science, vol 1643. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48481-7_45
Download citation
DOI: https://doi.org/10.1007/3-540-48481-7_45
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66251-8
Online ISBN: 978-3-540-48481-3
eBook Packages: Springer Book Archive