Random Schreier graphs and expanders
Let the group G act transitively on the finite set Ω, and let S⊆G be closed under taking inverses. The Schreier graph Sch(G↺Ω,S) is the graph with vertex set Ω and edge set {(ω,ωs):ω∈Ω,s∈S}. In this paper, we show that random Schreier graphs on Clog∣Ω∣ 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 Ω, 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.