Abstract
Let the group act transitively on the finite set , and let be closed under taking inverses. The Schreier graph is the graph with vertex set and edge set . In this paper, we show that random Schreier graphs on elements exhibit a (two-sided) spectral gap with high probability, magnifying a well known theorem of Alon and Roichman for Cayley graphs. On the other hand, depending on the particular action of on , we give a lower bound on the number of elements which are necessary to provide a spectral gap. We use this method to estimate the spectral gap when is nilpotent.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.