Let the group G act transitively on the finite set Omega, and let S subset of G be closed under taking inverses. The Schreier graph Sch(G (sic) Omega, S) is the graph with vertex set Omega and edge set {(omega,omega(s)) : omega is an element of Omega, s is an element of S}. In this paper, we show that random Schreier graphs on C log vertical bar Omega vertical bar 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 G on Omega, 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 G is nilpotent.
展开▼
