Random Schreier graphs and expanders

preprint2022arXivOpen access

Abstract

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

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.